% !TeX spellcheck = de_DE
\documentclass[UTF8,a4paper]{book} %设为A4纸
\usepackage{geometry}
\geometry{left=2cm,right=3cm,top=4cm,bottom=3cm} %设置页边距
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{verbatim}  %use verbatim
\usepackage{ctex}
\usepackage{ifthen}
\usepackage{makeidx}

\usepackage{extarrows} %use \xlongrightarrow
\usepackage{arydshln} %为了在array中使用：表示虚线

\usepackage{xcolor}
\colorlet{lightcyan}{cyan!40!white}
\usepackage{graphicx}
%\usepackage{chngcntr}
\usepackage{stackengine}

\usepackage{tasks}

\newlength{\longestlabel}

\settowidth{\longestlabel}{\bfseries viii.}

\usepackage[lastexercise]{exercise}
%\counterwithin{Exercise}{chapter}
%\counterwithin{Answer}{chapter}

%\renewcounter{Exercise}[chapter]

\setlength{\QuestionIndent}{7em}

\usepackage{enumerate}

\newboolean{printanswer}

%---------------------答案格式开始定义-----------------------------------------
%判断题后面加括号
\newcommand{\pd}[2][1]{\nolinebreak\dotfill\mbox{\raisebox{-1.8pt}
		{$\cdots$}(\makebox[#1 cm][c]{
			\ifthenelse{\boolean{printanswer}}
			{\ifthenelse{\equal{#2}{t}}{\Checkmark}{\XSolid}}
			{}
		})}}


%填空题画线  \tk
%\newcommand{\tk}[2][2.5]{\; \underline{\hspace{#1 cm} \hphantom{#2} \hspace{#1 cm} } \, }
\usepackage{ulem}
\newcommand{\tk}[2][0.5]{\;\uline{ 
		\hspace*{#1 cm}
		\ifthenelse{\boolean{printanswer}}{#2}{\hphantom{#2}}  
		\hspace*{#1 cm}
} }
%简答题  \jd
\newcommand{\jd}[2][4]{\par
	%\begin{minipage}[t][#1cm][t]{0.92\linewidth}	
		\ifthenelse{\boolean{printanswer}}{
			\begin{Answer}
				答：\par
				#2
			\end{Answer}
		}
		{}  
	%\end{minipage} 
}	
%---------------------------答案格式结束定义---------------------------------
\usepackage[breaklinks,colorlinks,linkcolor=black,citecolor=black,urlcolor=black]{hyperref} %生成pdf中的书签
\setboolean{printanswer}{true} %控制是否输出习题的答案


\begin{document}

\ifthenelse{\boolean{printanswer}}{
	\title{《现代密码学》习题集(2021)(有答案)}
}
{
	\title{《现代密码学》习题集(2021)(无答案)}
}


\maketitle

\tableofcontents	
	
\chapter{基本概念}
	\begin{Exercise}
		密码学中，把没有加密的消息和加密后的消息分别称为什么？英文单词是什么？
	\end{Exercise}
	\jd{
		密文 cipher text和明文plain text
	}

	\begin{Exercise}
		基本安全属性有哪些？
	\end{Exercise}
	\jd{
		安全属性，有时也称为安全目标，通常认为包括：
		\begin{enumerate}
			\item 机密性\textbf{Confidentiality}
			\item 完整性\textbf{Integrity}
			\item 非否认\textbf{Non-repudiation}
			\item 可认证\textbf{Authentication}
			\item 访问控制\textbf{Access Control}
		\end{enumerate}

	}

	\begin{Exercise}
	 给出被动攻击和主动攻击的定义，列出并简单定义各类攻击。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
   	\jd{
   		\begin{itemize}
   			\item 被动攻击，对系统的保密性进行攻击，如通过搭线窃听等，对文件或者程序的非负复制，以获得他人的信息。通常分为两类。
   			\begin{itemize}
   				\item 获取消息内容。
   				\item 进行业务流分析。
   			\end{itemize}
  				\item 主动攻击包括对数据流的篡改或产生某些假的数据流。主动攻击主要分为三类。
  				\begin{itemize}
  					\item 中断。
  					\item 篡改
  					\item 伪造
  				\end{itemize}
   		\end{itemize}
   	}
	  	
	\begin{Exercise}
		对抗被动攻击和主动攻击的一般性原则。
	\end{Exercise}
	\jd{
		被动攻击很难检测，所以对抗的重点是防范，而非检测。主动攻击想绝对防止很困难，对抗的主要方法是检测和恢复。
	}

   	\begin{Exercise}
   		柯克霍夫斯原则是什么？
   	\end{Exercise}
   	\jd{
   		柯克霍夫斯在其1883年出版的《军事密码学》一书中，提出“密码系统的安全性应该仅仅取决于所使用的密钥的机密性，而不是对该方案本身的保密”，这就是现在被大家广泛接受的“柯克霍夫斯原则”。
   	}
   	
   	\begin{Exercise}
   		什么是完全保密（perfect security）？
   	\end{Exercise}
   	\jd{
   		完全保密系统，通俗来讲，就是当我们获得密文后，对于我们了解明文，没有任何帮助。换句话说，消息M的概率为$P(M)$,在知道密文E的情况下，消息M的概率为$P_E(M)$，一个完全保密系统就是说对于所有可能的E和M，有$P(M)=P_E(M)$。
   	}
   
   	\begin{Exercise}
   		什么是一次一密？
   	\end{Exercise}
   	\jd{一次一密的重要特征是其密钥是一个随机序列，密钥只使用一次，且密钥的长度等
   		于明文序列的长度。一次一密理论上不可攻破的密码系统。也就是说一次一密系统是一
   		种完全保密系统，或者说是完全保密系统的一类实现。}
   	
   	\begin{Exercise}
   		密码攻击根据攻击者掌握的信息可以分为哪几种类型，并对每种类型做简单解释。
   	\end{Exercise}
   	\jd{
   		\begin{enumerate}
   			\item 密码分析员掌握除了密钥外，密码系统的加密和解密算法.
   			\item 仅知密文攻击(ciphertext-only attack)，密码分析员能够获得密文。.
   			\item 已知明文攻击(known-plaintext attack)，密码分析员能够获得某些明文和这些明文对应的密文.
   			\item 选择明文攻击(chosen-plaintext attack)，密码分析员能够有选择地获得明文和这些明文对应的密文.
   			\item 选择密文攻击(chosen-ciphertext attack)，密码分析员可以像合法用户那样发送加密的信息.
   			\item 密码分析员可以改变、截取或重新发送信息。
   		\end{enumerate}	
   }

   	\begin{Exercise}
   		简述密码体制的基本定义。
   	\end{Exercise}
   	\jd{
   		一个密码体制是指这样一种数学映射：
   		\begin{enumerate}
   			\item 明文消息空间M，某个字母表上的串集,M表示message。
   			\item 密文消息空间C，可能的密文消息集,C表示cipher。
   			\item 加密密钥空间$K_e$，可能的加密密钥集，K表示key，e表示encrypt。
   			\item 解密密钥空间$K_d$，可能的解密密钥集。d表示decryp。
   			\item 加密算法$E:M\times K_e \rightarrow C$,也可写为$c=E_{k_e}(m)$.
   			\item 加密算法$D:C\times K_d \rightarrow M$,也可写为$m=D_{k_d}(c)$.
   			\item 密码体制满足$D_{k_d}(E_{k_e}(m))=m$.
   		\end{enumerate}
   	}
   
   	\begin{Exercise}
   		什么是对称密码体制和非对称密码体制？
   	\end{Exercise}
   	\jd{
   		对称密码体制是指加密密钥和解密密钥相同的密码体制，反之称为非对称密码体制。
   	}
   
	\begin{Exercise}
	   	什么是计算安全？	   	
	\end{Exercise}
	\jd{
	   	如果破译者在选择最有效的算法前提以下，破解一个密码体制依然需要很大的资源，而这个资源是破译者无法承受的，那么我们称为这个密码体制是计算安全的。在通俗的来讲，就是“如果我们使用最好的算法来破译一个密码体制至少需
	   	要 n 次操作，而 n 是一个非常大的数，则我们称这个密码体制是计算上安全的"。
	}
	
	\begin{Exercise}
		密码学的两个分支是什么？	   	
	\end{Exercise}
	\jd{
		密码编码学和密码分析学
	}

\chapter{古典密码}
	\begin{Exercise}
		利用Caesar密码对nice进行加密，产生的密文是什么？\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		Caesar密码变换表如下所示：\par
		\begin{center}
			\begin{tabular}{|c|c||c|c|}
				\hline 
				明文& 密文 & 明文 & 密文 \\ 
				\hline 
				a& d & n & q \\ 
				\hline 
				b& e & o & r \\ 
				\hline 
				c& f & p & s \\ 
				\hline 
				d& g & q & t \\ 
				\hline 
				e& h & r & u \\ 
				\hline 
				f& i & s & v \\ 
				\hline 
				g& j & t & w \\ 
				\hline 
				h& k & u & x \\ 
				\hline 
				i& l & v & y \\ 
				\hline 
				j& m & w & z \\ 
				\hline 
				k& n & x & a \\ 
				\hline 
				l& o & y & b \\ 
				\hline 
				m& p & z & c \\ 
				\hline 
			\end{tabular} 
		\end{center}
		\par
		查表可得加密后的密文为：
		\textbf{qlfh}
	}

	\begin{Exercise}
		加法密码和Caesar密码之间的关系。
	\end{Exercise}
	\jd{Caesar是加法密码$k=3$的时的特例。}
	
	\begin{Exercise}
		设乘法密码的加密函数为$c=11m \pmod{26}$，则其解密密钥是多少？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$(11)^{-1} \pmod{26}=19 \pmod{26}$\par
		故此乘法密码的解密函数为：$m=19c \pmod{26}$\\
		\textbf{注：}\\
		1.验证：$11\times 19=209=26\times 8+1$\\
		2.求乘法逆元的算法之一：扩展欧几里得算法。
	}

	\begin{Exercise}
		仿射密码通用加密函数为$c=am+b \pmod{26}$,m为明文，c为密文，通常，我们把仿射密码体制中的什么看做此体制的密钥？\cite{mooc现代密码学聂旭云} 设想您采用了仿射加密，那么在相互传输消息时需要先把密钥告诉对方，假设密钥的交换采用文件方式，并且文件是通过安全信道传输，试想想有几种具体实现的方案，并实现验证。\\
		\textbf{提示:}\\
		1、可以直接将两个变量以二进制的方式写入文件，在使用时，依次读出。\\
		2、可以定义一个结构体，然后将此结构体直接写入文件，在使用时读出此结构体。\\
		3、如果是windows系统，可以使用windows的API WritePrivateProfileString和GetPrivateProfileString，具体可参考微软网站上的示例代码\url{https://docs.microsoft.com/en-us/windows/win32/api/winbase/nf-winbase-writeprivateprofilestringa}.当然，你也可以自定义函数，来实现WritePrivateProfileString和GetPrivateProfileString功能，以此来提高你程序的可移植性。Linux下有ini文件操作库，所以你可以定义一个接口库(一个函数壳)，根据不同的编译参数，决定链接windows库还是linux库，同样也可以提高程序的可移植性。
	\end{Exercise}
	\jd{我们把仿射密码体制中的a,b看成密钥。}
	
	\begin{Exercise}
		仿射密码加密函数为$c=17m+2 \pmod{26}$，求其解密函数？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$(17)^{-1} \pmod{26} = 23 \pmod{26}$\par
		解密函数为：$m=23(c-2) \pmod{26} \Rightarrow m=23c+6 \pmod{26}$
		\\
		\textbf{注：}\\
		1.验证：$17\times 23=391=26\times 15+1$\\
		2.验证：$23 \times 2=46=26+20,m=23c-20 \pmod{26}\rightarrow m=23c-20+26 \pmod{26} \rightarrow m=23c+6 \pmod{26}$\\
		3.求乘法逆元的算法之一：扩展欧几里得算法。
	}

	

	\begin{Exercise}
		已知敌手在用模26下的仿射密码加密，获取的密文为："gzyyf",已知明文是"he"开头，请破解此消息。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		26个字母分别和$0,1,2,\ldots$对应，h对应7，e对4，g对6，z对25，有：\\
		\[
		\begin{matrix}
			6=7a+b \pmod{26}\\
			25=4a+b \pmod{26}
		\end{matrix}
		\] 
		
		解得$a=11,b=7$，$a^{-1} \pmod {26}=19$，解密方程为$a^{-1} \left( x-b \right) \pmod {26}$，依次可求得yyf对应得明文为llo，故完整明文为：hello	
	}

	\begin{Exercise}
		设仿射变换的加密函数为：
		\[ E_{11,23}\left( m \right) ==11m+23 \pmod{26} \]
		请用此加密函数对明文"the national security agency"加密，并写出密文。解密变换为：
		\[ D_{11,23}\left( c \right) ==11^{-1}\left( c-23\right)  \pmod{26} \]
		对加密后的密文进行解密验证。\cite{yang-mcry}
	\end{Exercise}
	\jd{
	①明文m=THE NATIONAL SECURITY AGENCY用数字表示为：
	m=[19  7  4  13  0  19  8  14  13  0  11  18  4  2  20  17  8  19  24  0  6  4  13  2  24 ]
	根据${{E}_{11,23}}(m)\equiv 11m+23(\bmod 26)$，对明文中的每一个字符计算出相应的密文字符
	c=[24  22  15  10  23  24  7  21  10  23  14  13  15  19  9  2  7  24  1  23  11  15  10  19  1 ]
	由此得到密文c=YWPKXYHVKXONPTJCHYBXLPKTB
	②使用解密变换验证加密结果过程如下：
	由11*19≡1 (mod 26)知$11^{-1}=19$
	(注：求模逆元可以通过欧几里得算法或者直接穷举1~25)
	根据$D_{11,23}(c)≡19* (c-23) (mod 26)$，对密文中的每一个字符计算出相应的明文字符
	m=[19  7  4  13  0  19  8  14  13  0  11  18  4  2  20  17  8  19  24  0  6  4  13  2  24 ]
	由此得到m=THE NATIONAL SECURITY AGENCY，解密结果与明文一致，正确。
	
	}

	\begin{Exercise}
		用仿射变换对一个明文加密，得到的密文为：edsgickxhuklzveqzvkxwkzzukvcuh。已知明文的前两个字符为“if”，对该明文解密。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设加密变换为$c=E_{a,b}(m)≡a*m+b(mod 26)$
		由题目可知，明文前两个字符为if，相应密文为ed，即有：
		\[E(i)=e，4≡a*8+b(mod 26) ，(i=8，e=4)\]
		\[E(f)=d，3≡a*5+b(mod 26) ，(f=5，d=3)\]
		由上述两式可求得，a=9，b=10
		因此解密变换为$D_{9,10}(c)=9^{-1}*(c-10) (mod 26)$
		又由3*9≡1 (mod 26)可知9-1=3
		密文对应的数字表示为：
		c=[4  3  18  6  8  2  10  23  7  20  10  11  25  21  4  16  25  21  10  23  22  10  25  20  10  21  2  20  7 ]
		根据$D_{9,10}(c)=9^{-1}*(c-10) (mod 26)=3*(c-10) (mod 26)$，对密文中的每一个字符计算出相应的明文字符
		c=[8  5  24  14  20  2  0  13  17  4  0  3  19  7  8  18  19  7  0  13  10  0  19  4  0  7  2  4  17 ]
		由此得到明文m=ifyoucanreadthisthankateahcer
	}

	\begin{Exercise}
		一个多表替代的加密函数为:\\
		\begin{equation}
		\left( \begin{matrix}
		y_1\\
		y_2
		\end{matrix}\right) =\left( \begin{matrix}
		11&2\\
		5&23
		\end{matrix}\right) \left( \begin{matrix}
		x_1\\
		x_2
		\end{matrix}\right) \pmod {26}
		\end{equation}
		其中$\left( y_1,y_2\right) $为密文，$\left( x_1,x_2 \right) $为明文，计算该加密函数对应的解密函数。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		这道题问题是：求解密函数，这个问题可以转换为求逆矩阵，然后求逆矩阵可以有待定系数法(解方程法)、伴随矩阵法和初等变换法。我们下面简单说一下采用待定系数法。\par
		设逆矩阵为：\par
		\begin{equation}
		\left( \begin{matrix}
		a&b\\
		c&d
		\end{matrix}\right)
		\end{equation}
		根据逆矩阵的定义，我们有：\par
		
		\begin{equation}
		\left( \begin{matrix}
		11&2\\
		5&23
		\end{matrix}\right)  
		\left( \begin{matrix}
		a&b\\
		c&d
		\end{matrix}\right)
		 = \left( \begin{matrix}
		 1&0\\
		 0&1
		 \end{matrix}\right) \pmod {26}
		\end{equation}
		列出方程组为：
		$$ \left\{
		\begin{aligned}
		11a+2c=1 \pmod {26} \\
		11b+2d=0 \pmod {26} \\
		5a+23c=0 \pmod {26} \\
		5b+23d=1 \pmod {26}
		\end{aligned}
		\right.
		$$
		可以利用消元法，得到：$a=17,b=20,c=11,d=7$
		即：
		\begin{equation}
		\left( \begin{matrix}
		11&2\\
		5&23
		\end{matrix}\right)^{-1}  \pmod {26} =
		\left( \begin{matrix}
		17&20\\
		11&7
		\end{matrix}\right)
		\end{equation}
	}

	\begin{Exercise}
		设多表代换密码中
		$A=\left( \begin{matrix}
		3 & 13 & 21 & 9  \\
		15 & 10 & 6 & 25  \\
		10 & 17 & 4 & 8  \\
		1 & 23 & 7 & 2  \\
		\end{matrix} \right),B=\left( \begin{matrix}
		1  \\
		21  \\
		8  \\
		17  \\
		\end{matrix} \right)$
		加密为：${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$,对明文“PLEASE SEND ME THE BOOK,MY CREDIT CARD NO IS SIX ONE TWO ONE THREE EIGHT SIX ZERO ONE SIX EIGHT FOUR NINE SEVEN ZERO TWO”用解密变换 :${{M}_{i}}\equiv {{A}^{-1}}+B{{(\bmod 26)}_{{}}}$验证你的结果，其中${{A}^{-1}}=\left( \begin{matrix}
		23 & 13 & 20 & 5  \\
		0 & 10 & 11 & 0  \\
		9 & 11 & 15 & 22  \\
		9 & 22 & 6 & 25  \\
		\end{matrix} \right)$
		.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		加密时，先将明文分组，每四个一组：\\
		$
		{{M}_{1}}\equiv 
		\left[ 
			\begin{matrix}
				15  \\
				11  \\
				4  \\
				0  \\
			\end{matrix} 
		\right]
		{{M}_{2}}\equiv 
		\left( \begin{matrix}
					18  \\
					4  \\
					18  \\
					4  \\
				\end{matrix} 
		\right){{M}_{3}}\equiv 
		\left( \begin{matrix}
					13  \\
					3  \\
					12  \\
					4  \\
				\end{matrix} 
		\right){{M}_{4}}\equiv 
		\left( \begin{matrix}
					19  \\
					7  \\
					4  \\
					1  \\
				\end{matrix} 
		\right){{M}_{5}}\equiv 
		\left( \begin{matrix}
					14  \\
					14  \\
					10  \\
					12  \\
				\end{matrix} 
		\right){{M}_{6}}\equiv 
		\left( \begin{matrix}
					24  \\
					2  \\
					17  \\
					4  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{7}}\equiv 
		\left( \begin{matrix}
					3  \\
					8  \\
					19  \\
					2  \\
				\end{matrix} 
		\right){{M}_{8}}\equiv 
		\left( \begin{matrix}
					0  \\
					17  \\
					3  \\
					13  \\
				\end{matrix} 
		\right){{M}_{9}}\equiv 
		\left( \begin{matrix}
					14  \\
					8  \\
					18  \\
					18  \\
				\end{matrix} 
		\right){{M}_{10}}\equiv 
		\left( \begin{matrix}
					8  \\
					23  \\
					14  \\
					13  \\
				\end{matrix} 
		\right){{M}_{11}}\equiv 
		\left( \begin{matrix}
					4  \\
					19  \\
					22  \\
					14  \\
				\end{matrix} 
		\right){{M}_{12}}\equiv 
		\left( \begin{matrix}
					14  \\
					13  \\
					4  \\
					19  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{13}}\equiv 
		\left( \begin{matrix}
					7  \\
					17  \\
					4  \\
					4  \\
				\end{matrix} 
		\right){{M}_{14}}\equiv 
		\left( \begin{matrix}
					4  \\
					8  \\
					6  \\
					7  \\
				\end{matrix} 
		\right){{M}_{15}}\equiv 
		\left( \begin{matrix}
					19  \\
					18  \\
					8  \\
					23  \\
				\end{matrix} 
		\right){{M}_{16}}\equiv 
		\left( \begin{matrix}
					25  \\
					4  \\
					17  \\
					4  \\
				\end{matrix} 
		\right){{M}_{17}}\equiv 
		\left( \begin{matrix}
					14  \\
					13  \\
					4  \\
					18  \\
				\end{matrix} 
		\right){{M}_{18}}\equiv 
		\left( \begin{matrix}
					8  \\
					23  \\
					4  \\
					8  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{19}}\equiv 
		\left( \begin{matrix}
					6  \\
					7  \\
					19  \\
					5  \\
				\end{matrix} 
		\right){{M}_{20}}\equiv 
		\left( \begin{matrix}
					14  \\
					20  \\
					17  \\
					13  \\
				\end{matrix} 
		\right){{M}_{21}}\equiv 
		\left( \begin{matrix}
					8  \\
					13  \\
					4  \\
					18  \\
				\end{matrix} 
		\right){{M}_{22}}\equiv 
		\left( \begin{matrix}
					4  \\
					21  \\
					4  \\
					13  \\
				\end{matrix} 
		\right){{M}_{23}}\equiv 
		\left( \begin{matrix}
					25  \\
					4  \\
					17  \\
					14  \\
				\end{matrix} 
		\right){{M}_{24}}\equiv 
		\left( \begin{matrix}
					19  \\
					22  \\
					14  \\
					{}  \\
				\end{matrix} 
		\right) 
		$
		再代入加密变换：${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$,得到计算结果：\\
		
		$
		{{C}_{1}}\equiv \left( \begin{matrix}
		13  \\
		16  \\
		23  \\
		1  \\
		\end{matrix} \right){{C}_{2}}\equiv \left( \begin{matrix}
		1  \\
		19  \\
		22  \\
		1  \\
		\end{matrix} \right){{C}_{3}}\equiv \left( \begin{matrix}
		3  \\
		2  \\
		9  \\
		9  \\
		\end{matrix} \right){{C}_{4}}\equiv \left( \begin{matrix}
		8  \\
		9  \\
		3  \\
		19  \\
		\end{matrix} \right){{C}_{5}}\equiv \left( \begin{matrix}
		23  \\
		3  \\
		2  \\
		5  \\
		\end{matrix} \right){{C}_{6}}\equiv \left( \begin{matrix}
		24  \\
		5  \\
		18  \\
		6  \\
		\end{matrix} \right) \\ 
		{{C}_{7}}\equiv \left( \begin{matrix}
		11  \\
		24  \\
		6  \\
		3  \\
		\end{matrix} \right){{C}_{8}}\equiv \left( \begin{matrix}
		12  \\
		14  \\
		23  \\
		13  \\
		\end{matrix} \right){{C}_{9}}\equiv \left( \begin{matrix}
		11  \\
		11  \\
		6  \\
		13  \\
		\end{matrix} \right){{C}_{10}}\equiv \left( \begin{matrix}
		7  \\
		0  \\
		15  \\
		2  \\
		\end{matrix} \right){{C}_{11}}\equiv \left( \begin{matrix}
		16  \\
		25  \\
		25  \\
		16  \\
		\end{matrix} \right){{C}_{12}}\equiv \left( \begin{matrix}
		25  \\
		2  \\
		17  \\
		6  \\
		\end{matrix} \right) \\ 
		{{C}_{13}}\equiv \left( \begin{matrix}
		25  \\
		4  \\
		25  \\
		9  \\
		\end{matrix} \right){{C}_{14}}\equiv \left( \begin{matrix}
		20  \\
		8  \\
		4  \\
		1  \\
		\end{matrix} \right){{C}_{15}}\equiv \left( \begin{matrix}
		17  \\
		17  \\
		18  \\
		16  \\
		\end{matrix} \right){{C}_{16}}\equiv \left( \begin{matrix}
		13  \\
		4  \\
		12  \\
		21  \\
		\end{matrix} \right){{C}_{17}}\equiv \left( \begin{matrix}
		16  \\
		3  \\
		9  \\
		4  \\
		\end{matrix} \right){{C}_{18}}\equiv \left( \begin{matrix}
		12  \\
		23  \\
		13  \\
		0  \\
		\end{matrix} \right) \\ 
		{{C}_{19}}\equiv \left( \begin{matrix}
		8  \\
		4  \\
		17  \\
		15  \\
		\end{matrix} \right){{C}_{20}}\equiv \left( \begin{matrix}
		23  \\
		0  \\
		10  \\
		12  \\
		\end{matrix} \right){{C}_{21}}\equiv \left( \begin{matrix}
		24  \\
		17  \\
		1  \\
		24  \\
		\end{matrix} \right){{C}_{22}}\equiv \left( \begin{matrix}
		19  \\
		16  \\
		5  \\
		12  \\
		\end{matrix} \right){{C}_{23}}\equiv \left( \begin{matrix}
		13  \\
		4  \\
		12  \\
		21  \\
		\end{matrix} \right){{C}_{24}}\equiv \left( \begin{matrix}
		14  \\
		12  \\
		4  \\
		{}  \\
		\end{matrix} \right) \\ 
		$

		知密文为：\par
		NQXB  BTWB  DCJJ  IJDT  XDCF  YFSG \par
		LYGD  MOXN  LLGN  HAPC  QZZQ  ZCRG \par
		ZEZJ  UIEB  RRSQ  NEMV  QDJE  MXNA \par
		IERP  XAKM  YRBY  TQFM  NEMV  OME \par
		同上，解密时，先将密文分组，再代入解密变换：${{M}_{i}}\equiv {{A}^{-1}}+B{{(\bmod 26)}_{{}}}$\\
		得到明文：
		PLEA  SESE  NDME  THEB  OOKM  YCRE \par
		DITC  ARDN  OISS  IXON  ETWO  ONET \par
		HREE  EIGH  TSIX  ZERO  ONES   IXEI \par
		GHTF  OURN  INES  EVEN  ZERO  TWO\par
		解密验证结果与明文相符。
		
	}
	\begin{Exercise}
		设多表代换密码 ${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$ 中，A是2×2矩阵，B是零矩阵，又知明文“dont”被加密为“elni”，求矩阵A。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设矩阵 $A\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)$
		
		由m=dont=(3,14,13,19)，c=elni=(4,11,13,8)可知:
		\[
		\left( \begin{matrix}
		4  \\
		11  \\
		\end{matrix} \right)\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)\left( \begin{matrix}
		3  \\
		14  \\
		\end{matrix} \right)\text{(mod}26)
		\]

		\[		
		\left( \begin{matrix}
		13  \\
		8  \\
		\end{matrix} \right)\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)\left( \begin{matrix}
		13  \\
		9  \\
		\end{matrix} \right)\text{(mod}26)
		\]
		我们可以得到两个方程组：
		
		$$ \left\{
		\begin{aligned}
		4 =3a+14b \pmod {26} \\
		13=13a+9b \pmod {26} 
		\end{aligned}
		\right.
		$$	
		
		$$ \left\{
		\begin{aligned}
		11 =3c+14d \pmod {26} \\
		8=13c+9d \pmod {26} 
		\end{aligned}
		\right.
		$$		
	
		分别解上述两个方程组可得：$a=10,b=13,c=9,d=23$.即：\par
		\[
		A\equiv \left( \begin{matrix}
		10 & 13  \\
		9 & 23  \\
		\end{matrix} \right)
		\]	
	}


\chapter{流密码}
	\begin{Exercise}
		流密码是属于哪种密码体制？
	\end{Exercise}
	\jd{流密码是对称密码体制。}
	
	\begin{Exercise}
		简述Golomb的随机性公设。
	\end{Exercise}
	\jd{
		Golomb 提出了伪随机周期序列应该满足 3 个随机性公设：\par
		1. 在序列的一个周期内，0 与 1 的个数相差最多为 1.\par
		2. 在序列的一个周期内，长为 1 的游程占游程总数的$\dfrac{1}{2}$ ，长为 2 的游程占游程总数的$\dfrac{1}{2^2}$, 长为 i 的游程占游程总数的$\dfrac{1}{2^i}$，且在等长的游程中 0 的游程个数与 1的游程个数相等。\par
		3. 异自相关函数是一个常数。
	}
	
	\begin{Exercise}
		在序列密码中，分别有哪两种加密方式？
	\end{Exercise}
	\jd{在序列密码中有同步加密方式和自同步加密方式}
	
	\begin{Exercise}
		序列密码设计的核心问题是什么？
	\end{Exercise}
	\jd{序列密码设计的核心问题是密钥序列发生器的设计。}
	
%	\begin{Exercise}
%		线性同余算法${{X}_{\text{n+1}}}\text{=}\left( a{{X}_{n}} \right)\bmod {{2}^{4}}$，问：\\
%		（1）该算法产生的数列的最大周期是多少？\\
%		（2）a的值是多少？\\
%		（3）对种子有何限制？
%		\cite{yang-mcry}
%	\end{Exercise}
%	\jd{
%		(1)由于模$\text{m}={{2}^{4}}$因此它没有原根，又由递推式不难得知${{X}_{\text{n}}}\text{=}{{\text{a}}^{n}}{{X}_{0}}\bmod {{2}^{4}}$。因此该算法产生的序列的最大周期为$\text{a}\bmod {{2}^{4}}$的最大阶l，而$l|\varphi \left( {{2}^{4}} \right)$，但$l\ne \varphi \left( {{2}^{4}} \right)\text{=}8$。若l=4，则不难验证，${{X}_{0}}=1$，$a=3$时，数列周期为4，因此该算法产生数列的最大周期是4。
%		\par
%		(2)a必须满足$\gcd \left( a,{{2}^{4}} \right)=1$，所以a在$\left\{ 1,3,5,...,15 \right\}$中取值。
%		周期为4的有$\left\{ 3,5,11,13 \right\}$，即为a的取值.		
%		\par
%		(3)种子${{X}_{0}}$必须满足$\gcd \left( {{X}_{0}},{{2}^{4}} \right)=1$。
%	}
	
	
	\begin{Exercise}
		设一个3级线性反馈移位寄存器(LFSR)的特征多项式为$f(x)=1+x^2+x^3$.\\
		(1)画出该LFSR的框图。\\
		(2)给出序列的递推关系式。\\
		(3)设初始状态$(a_0,a_1,a_2)=(0,0,1)$,写出输出序列级序列及周期。\\
		(4)列出序列的游程。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		(1)LFSR的框图如\ref{fig:lfsr}所示。
		\par
		(2)输出序列的递推关系为：$a_n = a_{n-2} + a_{n-3}\quad n=3,4,5,\ldots$
		\par
		(3)初始状态为$(a_0,a_1,a_2)=(0,0,1)$，输出序列为：
		\[\underline{0010111} 0010111  \ldots  \]
		周期为7.
		\par
		(4)0的1游程，1个；1的1 游程，1个；0的2游程1个；1的3游程1个。
	}

	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.6\linewidth] {ex2-1.png}
		\caption{LFSR框图}
		\label{fig:lfsr}
	\end{figure}

	\begin{Exercise}
		(1)已知流密码的密文串$1010110110$，相应的明文串$0100010001$，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破解该密码系统。\cite{mooc现代密码学聂旭云}\par
		(2)现在我们获得了后续的密文串$111000111000$，请问明文是什么？
	\end{Exercise}
	\jd{
	(1)首先计算密钥串：\\
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
			\hline 
			明文 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 
			\hline 
			密文 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 
			\hline 
			密钥 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 
			\hline 
		\end{tabular}  \par
		密钥流为：1110100111.\par
		3级移位寄存器通式：
		\[
		\left\lbrace \begin{matrix}
			a_3 = c_1 a_2 \oplus c_2 a_1 \oplus c_3 a_0\\
			a_4 = c_1 a_3 \oplus c_2 a_2 \oplus c_3 a_1\\
			a_5 = c_1 a_4 \oplus c_2 a_3 \oplus c_3 a_2\\
		\end{matrix}
		\right.
		\]
		用已知的明文和密文对应关系，可以得：
		\[
		\left\lbrace \begin{matrix}
		0 = c_1  \oplus c_2  \oplus c_3 \\
		1 = c_2  \oplus c_3 \\
		0 = c_1  \oplus c_3 \\
		\end{matrix}
		\right.
		\]
		写成矩阵形式：
		\[\begin{bmatrix}0&1&0 \end{bmatrix}=\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}
		\begin{bmatrix}
		1 & 0 & 1\\
		1 & 1 & 0 \\
		1 & 1 & 1 \\
		\end{bmatrix}
		\]
		利用Gauss-Jordan算法求逆矩阵：\\
		$\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		1 & 1 & 0 &   0 & 1 & 0 \\
		1 & 1 & 1 &   0 & 0 & 1 \\
		\end{array}	\right] \xlongrightarrow{\substack{R_1+R_2 \\ R_1+R_3}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		0 & 1 & 1 &   1 & 1 & 0 \\
		0 & 1 & 0 &   1 & 0 & 1 \\
		\end{array}	\right] \xlongrightarrow{\substack{R_2+R_3}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		0 & 1 & 1 &   1 & 1 & 0 \\
		0 & 0 & 1 &   0 & 1 & 1 \\
		\end{array}	\right]  \xlongrightarrow{\substack{R_3+R_1 \\ R_3+R_2}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 0 &   1 & 1 & 1 \\
		0 & 1 & 0 &   1 & 0 & 1 \\
		0 & 0 & 1 &   0 & 1 & 1 \\
		\end{array}	\right]
		$\par
		我们有：\\
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}0&1&0 \end{bmatrix}
		\begin{bmatrix}
		1 & 0 & 1\\
		1 & 1 & 0 \\
		1 & 1 & 1 \\
		\end{bmatrix}^{-1}
		\]
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}0&1&0 \end{bmatrix}
		\begin{bmatrix}
		1 & 1 & 1\\
		1 & 0 & 1 \\
		0 & 1 & 1 \\
		\end{bmatrix}
		\]
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}1 & 0 &1 \end{bmatrix}\]
		\par
		解得$c_1=1,c_2=0,c_3=1$。\par
		递推关系为$a_{n-1} = a_n + a_{n-2}$或$a_3 = a_2 +a_0$.
	(2)需要解密的是12bit，前面我们已经获得前序10bit密钥，根据递推关系，我们计算后12bit的密钥：
	$
	a_7=1,a_8=1,a_9=1;\\
	a_{10}=0;\\
	a_{11}=1;\\
	a_{12}=0;\\
	a_{13}=0;\\
	a_{14}=1;\\
	a_{15}=1;\\
	a_{16}=1;\\
	a_{17}=0;\\
	a_{18}=1;\\
	a_{19}=0;\\
	a_{20}=0;\\
	a_{21}=1;\\
	$\par
	计算明文：\par
	\begin{tabular}{ccccccccccccc}
		%\hline 
		密文&  1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0  \\ 
		\hline 
		密钥&  0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 
		\hline 
		明文&  1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 
		%\hline 
	\end{tabular} 
	}

	\begin{Exercise}
		3级线性反馈移位寄存器在 ${{c}_{3}}=1 $时可有4种线性反馈函数，设其初始状态为$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}} \right)=\left( 1,0,1 \right)$ ，求各线性反馈函数的输出序列及周期。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设3级线性反馈特征多项式为$p\left( x \right)=1+{{c}_{1}}x+{{c}_{2}}{{x}^{2}}+{{c}_{3}}{{x}^{3}}$ ，若${{c}_{3}}=1$ 则共有 ${{2}^{2}}=4$种可能的特征多项式,分别为：
		\[{{p}_{1}}\left( x \right)=1+{{x}^{3}}\]
		\[{p}_{2}\left( x \right)=1+x+{x}^{3}\]
		\[{p}_{3}\left( x \right)=1+{{x}^{2}}+{x}^{3}\]
		\[{p}_{4}\left( x \right)=1+x+{{x}^{2}}+{x}^{3}\]
	
		初态$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}} \right)=\left( 1,0,1 \right)$ 。则4种线性反馈函数输出序列分别为：\\
		${{p}_{1}}$输出序列 $a=\overbrace{\underline{101}}\overbrace{101}\underbrace{101}\overbrace{101}\overbrace{101}101\cdots $，周期为3\\
		${p}_{2}$输出序列$a=\overbrace{\underline{101}0011}\overbrace{1010011}\overbrace{1010011}\overbrace{1010011}\overbrace{1010011}10\cdots$, 周期为7，是m序列\\
		${p}_{3}$输出序列 $a=\overbrace{\underline{101}}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}10\cdots$，周期为3\\
		${p}_{4}$输出序列 $a=\underline{101}0\overbrace{10}\overbrace{10}\overbrace{10}101010101\cdots $，周期为2\\
	}


	
	\begin{Exercise}
		设 n=4，$f\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)={{a}_{1}}\oplus {{a}_{4}}\oplus 1\oplus {{a}_{2}}{{a}_{3}}$ ，初始状态为$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)=\left( 1,1,0,1 \right)$ ，求此非线性反馈移位寄存器的输出序列及周期。.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由 $f\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)={{a}_{1}}\oplus {{a}_{4}}\oplus 1\oplus {{a}_{2}}{{a}_{3}}$，初态为 $\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)=\left( 1,1,0,1 \right)$ 。线性递归可得：\\
		$
		{{a}_{5}}=1\oplus 1\oplus 1\oplus 0=1 \\
		{{a}_{6}}=1\oplus 1\oplus 1\oplus 0=1\\
		{{a}_{7}}=0\oplus 1\oplus 1\oplus 1=1\\
		{{a}_{8}}=1\oplus 1\oplus 1\oplus 1=0\\
		{{a}_{9}}=1\oplus 0\oplus 1\oplus 1=1\\
		{{a}_{10}}=1\oplus 1\oplus 1\oplus 0=1
		$
		可以得到输出序列为 $\left( 1101111011\cdots  \right)$，周期为p=5 。
	}
	
	


	\begin{Exercise}
		若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器，产生的密钥是m序列。敌手若知道一段长为2n的明密文对就可破译密钥流生成器。若敌手仅知道长为2n-2的明密文对，问如何破译密钥流生成器。.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		如果敌手仅仅知道长为2n-2的明密文对，他可以构造出以下的长为2n的明密文对：
		不妨设：\par
		明文：${{x}_{1}}{{x}_{2}}...{{x}_{2n-2}}{{x}_{2n-1}}{{x}_{2n}}$ \par
		密文：${{y}_{1}}{{y}_{2}}...{{y}_{2n-2}}{{y}_{2n-1}}{{y}_{2n}}$\par
		其中：\par
		${{x}_{1}}\cdots \cdots {{x}_{2n-2}}$ 为已知的， ${{x}_{2n-1,}}{{x}_{2n}}$为未知的。\par
		${{y}_{1}}\cdots \cdots {{y}_{2n-2}}$为已知的， ${{y}_{2n-1,}}{{y}_{2n}}$为未知的。\par
		
		 $({{y}_{2n-1,}}{{y}_{2n}})$的可能取值为{00,01,10,11}。 $({{x}_{2n-1,}}{{x}_{2n}})$的可能取值为{00,01,10,11}。共有16种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为正确的方案，有可能不唯一。
		
	}


	\begin{Exercise}
		Geffe序列发生器由3个LFSR组成，这些LFSR的长度分别为$n_i \quad i=1,2,3$,其输出序列均为m序列，则Geffe序列产生器的线性复杂度是多少？\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{($n_1 +n_3) n_2 +n_3$}
	
\chapter{分组密码}
	\begin{Exercise}
		什么是Feistel结构？
	\end{Exercise}
	\jd{
		把整个Feistel网络画出来，并进行描述。
	}
	
	\begin{Exercise}
	分组密码设计的基本原则？
	\end{Exercise}
	\jd{混淆和扩散}
	
	\begin{Exercise}
		除了混淆和扩散原则，分组密码算法还应满足哪些要求？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item 分组长度n要足够大：防止明文穷举攻击法奏效。
			\item 密钥量要足够大：尽可能消除弱密钥，并使所有密钥同等地好，以防止密钥穷举攻击奏效。
			\item 由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。
			\item 加密和解密运算简单：易于软件和硬件高速实现。
			\item 数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时，可引入数据扩展。
		\end{enumerate}
	}
	
	\begin{Exercise}
		请简述常用的五种分组密码的工作方式。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item 电码本(ECB):直接利用加密算法分别对分组数据组加密。
			\item 密码分组链接模式(CBC):先将明文分组与上一次的密文块进行按比特异或，然后进行加密处理。
			\item 密码反馈模式(CFB):若待加密消息需按字符、字节或比特处理时，可采用CFB模式。
			\item 输出反馈模式(OFB):在结构熵类似CFB模式，但其反馈的内容是DES的输出，而不是密文。
			\item 计数器模式：可以看做是OFM模式的简化版本，其输入由计数器来更新。
		\end{enumerate}
	}
	
	
	
	\begin{Exercise}
		(1) 设$M^{'}$是M的逐比特取补，证明在DES中，如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即：\par
		如果$Y=DES_K(X)$，那么$Y^{'}=DES_{K^{'}}(X^{'})$
		\par
		提示：对任意两个长度相等的比特串A和B，证明$A^{'}\oplus B^{'}=A\oplus B$ 。
		\par
		(2) 对DES进行穷搜索攻击时，需要在由$2^{56}$个密钥构成的密钥空间进行，能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)我们先看一下异或取补的运算律：\\
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|}
				\hline 
				M                  & 0 & 0 & 1 & 1 \\ 
				\hline 
				K                  & 1 & 0 & 1 & 0 \\ 
				\hline 
				$M\oplus K$        & 1 & 0 & 0 & 1 \\ 
				\hline 
				$M^{'}$            & 1 & 1 & 0 & 0 \\ 
				\hline 
				$K^{'}$            & 0 & 1 & 0 & 1 \\ 
				\hline 
				$M^{'}\oplus K^{'}$& 1 & 0 & 0 & 1 \\ 
				\hline 
				$(M\oplus K)^{'}$  & 0 & 1 & 1 & 0 \\ 
				\hline 
				$M\oplus K^{'}$    & 0 & 1 & 1 & 0 \\ 
				\hline 
				$M^{'}\oplus K$    & 0 & 1 & 1 & 0 \\ 
				\hline 
			\end{tabular}
		\end{center}
		\par
		我们有：
		\[M\oplus K = M^{'}\oplus K^{'}  \]
		\[(M\oplus K)^{'}=M\oplus K^{'}= M^{'}\oplus K\]
	设$L_i$和$R_i$分别是第i轮DES变换的左右部分，$i=0,1,…,16$, 则加密过程为:\\
		$
		L_0 R_0 \leftarrow IP(X) \\ 
		L_i \leftarrow R_{i-1} \\ 
		R_i \leftarrow L_{i-1}\oplus f(R_{i-1},K_{i}) \\ 
		64bit\ cipher\ Y \leftarrow IP^{-1}(R_{16} L_{16}) \\ 
		$\par
	若将明文$X$和密钥$K$同时取补后为$X^{'},K^{'}$，则加密过程为：\\
		$
		L_0^{'} R_{0}^{'}\leftarrow IP(X^{'}) \\ 
		L_{i}^{'}\leftarrow R_{i-1}^{'}  \\ 
		$
		计算：\[L_{i-1}^{'}\oplus f(R_{i-1}^{'},K_{i}^{'})\]
		其中，$f(R_{i-1},K_{i})$ 的作用是将数据的左、右半部分扩展后与密钥进行逐比特异或运算，因此 \[f(R_{i-1},K_{i})=f(R^{'}_{i-1},K^{'}_{i})\]
		再经过S盒，并将输出结果进行置换运算P之后有：
		\[ L^{'}_{i-1}\oplus f(R^{'}_{i-1},K^{'}_{i})
		=L{{'}_{i-1}}\oplus f({{R}_{i-1}},{{K}_{i}})
		=(L_{i-1}\oplus f(R_{i-1},K_{i}))^{'}
		=R_i^{'}
		\] \\
		
		所以有 
		\[ R_i^{'} \leftarrow L_{i-1}^{'}\oplus f(R_{i-1}^{'},K_{i}^{'})\]
		
		\[ 64bit\ cipher\ \bar{Y} \leftarrow IP^{-1}(R_{16}^{'}L_{16}^{'}) 
		=(IP^{-1}(R_{16} L_{16}))^{'}
		=Y^{'}
		\] 
		综上所述，我们知，明文$X$与密钥$K$同时取补后有$Y^{'}=DES_{K^{'}}(X^{'})$ 。
		\par
		(2)根据(1)的结论进行穷搜索攻击, 可将待搜索的密钥空间减少一半，即$2^{55}$个。因为给定明文$X$，则 $Y_1=DES_{K}(X)$，由(1)知 $Y_2=DES_{K^{'}}(X^{'})=Y_{1}^{'}$，则一次搜索就包含了$X$和$X^{'}$ 两种明文情况。
	
	}

	\begin{Exercise}
		证明DES解密变换是加密变换的逆。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		令 $T(L,R)=(R,L)$为左右位置交换函数,$ F_{k_i}=(L\oplus f(R,k_i),R) $.
		则第i次迭代变换为:
		\[ T_{k_i}=T{F_{k_i}}=T(L\oplus f(R,k_i),R)=(\text{R},L\oplus f(R,k_i)) \]
		\par
		
		又因为：\[ T^2(L,R)=I(L,R) \]
		我们有：\[ T=T^{-1} \]
		同时:\[ F_{k_i}^{2}(L,R)=F_{k_i}(L\oplus f(R,k_i),R)=(L\oplus f(R,k_i)\oplus f(R,k_i),R)=(L,R)\]
		即:
		\[ F_{k_i}=F_{k_i}^{-1} \]
		
		所以有:
		\[
		(F_{k_i}T)(TF_{k_i})
		=F_{k_i}F_{k_i}
		=I
		\Rightarrow {TF_{k_i}}^{-1}=F_{k_i}T
		\]
		
		DES加密过程在密钥k作用下为:
		\[
		DES_{k}=(IP^{-1}) F_{k_{16}} T F_{k_{15}} T \cdots F_{k_2} T F_{k_1} (IP)
		\]
		
		解密过程为:
		\[
		DES_k^{-1}
		=((IP^{-1}) F_{k_{16}} T F_{k_{15}} T \cdots F_{k_2} T F_{k_1} (IP))^{-1}
		=IP^{-1} F_{k_1} T F_{k_2} T \cdots F_{k_{15}} T F_{k_{16}} (IP)
		\]
	
		我们把$DES_k^{-1}$和$DES_k$的展开式相乘，可知：
		\[
		 DES_k^{-1} DES_k =I
		\]
		即解密变换是加密变换的逆。（得证）
	}

	\begin{Exercise}
		在DES的EBC模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组
		受到影响。然而在CBC模式中，将有错误传播。例如在图\ref{fig:CBC}中,C1中的一个错误明显地将影响解密获得的P1和P2的结果。\par
		(1)  P2后的分组是否受到影响？\par
		(2) 设加密前的明文分组P1中有一个比特的错误，问这一错误将在多少个密文分组中传播？对接收者产生什么影响？
		。\cite{yang-mcry}\par		
	\end{Exercise}
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\linewidth] {CBC.png}
	\caption{DES的CBC模式}
	\label{fig:CBC}
\end{figure}
	\jd{
		(1)在CBC模式中，若密文分组中有一个错误$C_1$，则解密时明文分组中$P_1,P_2$ 都将受到影响，而$P_{2+i}(i=1,2,\cdots)$ 后的分组都不受影响，即CBC的错误传播长度为2，具有自恢复能力。
		\par
		(2)若明文分组$P_1$有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解密后，除$P_1$有错误外，其余的明文分组都能正确恢复。
	}

	\begin{Exercise}
		在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远？\cite{yang-mcry}
	\end{Exercise}
	\jd{
		在8比特CFB模式中，若密文有1比特错误，除了影响当前分组解密结果，这8比特会填充到下一个解密的移位寄存器的低8位，只有再移8次才能全部移出移位寄存器，所以，会使解密输出连续9组出错，即错误传播的长度为9。
	}

	\begin{Exercise}
		证明SM4算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		SM4算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理，E进行数据顺序交换。即加密轮函数:\par
		\begin{center}
			$F_i=G_i E$
		\end{center}
		
		\par
		其中：
		\begin{align}
			G_i &=G_i(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)\quad (i=0,1,2,…,31)\\
			    &=(X_i \oplus T( X_{i+1},X_{i+2},X_{i+3},rk_i),X_{i+1},X_{i+2},X_{i+3})
		\end{align}
		
		\par
		\begin{align}
			&E(X_{i+4},(X_{i+1},X_{i+2},X_{i+3}))\\
			&=((X_{i+1},X_{i+2},X_{i+3}),X_{i+4}) \quad (i=0,1,2,…,31)
		\end{align}
	
		因为有：
		\begin{align}
			(G_i)^2 &=G_i G_i(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)\\
			        &=G_i(X_i \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i),X_{i+1},X_{i+2},X_{i+3},rk_i)\\
			        &=(X_i \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i) \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i), X_{i+1},X_{i+2},X_{i+3},rk_i)\\
			        &=(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)\\
			        &=I
		\end{align}
		
		因此，加密函数G是对合得。\par
		E变换为：
		\begin{align}
			E(X_{i+4},(X_{i+1},X_{i+2},X_{i+3}))\\
			=((X_{i+1},X_{i+2},X_{i+3}),X_{i+4})
		\end{align}
		我们有：
		
		\[ E^2 (X_{i+4},(X_{i+1},X_{i+2},X_{i+3})) =I \]
		
		显然，E是对合运算。\par
		综上，加密轮函数是对合的。\par
		根据加密框图，可将SM4的加密过程写为：\par
		\begin{align}
			SM4=G_0 EG_1 E \ldots G_{30} EG_{31} R
		\end{align}
		\par
		根据解密框图，可将SM4的解密过程写为：\par
		\begin{align}
			SM4^{-1}=G_{31} EG_{30} E…G_1 EG_0 R
		\end{align}
		比较SM4与$SM4^{-1}$可知，运算相同，只有密钥的使用顺序不同。\par
		所以，SM4算法是对合的。
	}


\chapter{数论基本练习}

	\begin{Exercise}
		求$\gcd (4655,12075)$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由Euclid算法，得：\par
		\[12075=2\times 4655+2765 \]  
		\[ 4655=1\times 2765+1890 \]  
		\[ 2765=1\times 1890+875 \]  
		\[ 1890=2\times 875+140 \]  
		\[ 875=6\times 140+35 \]  
		\[ 140=4\times 35+0 \]  
	
		\par
		所以$\gcd (4655,12075)=35$。	
	}
	
	
	\begin{Exercise}
	证明：如果a是整数，则$a^3 -a$一定能被3整除。
	\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$\because a^3-a=(a-1)a(a+1)$\par
		当$a=3k,k \in \mathbb{Z}$,则$(a-1)a(a+1)=(3k-1)3k(3k+1)$，一定能被3整除。\par
		当$a=3k-1,k \in \mathbb{Z}$,则$(a-1)a(a+1)=(3k-2)(3k-1)3k$，一定能被3整除。\par
		当$a=3k+1,k \in \mathbb{Z}$,则$(a-1)a(a+1)=3k(3k+1)(3k+2)$，一定能被3整除。\par
		综上所述，$a^3 -a$一定能被3整除。
	}

	\begin{Exercise}
		证明以下关系\cite{yang-mcry}：\par
		(1) $a \pmod n = b \pmod n \Rightarrow a =b \pmod n$ \par
		(2) $a\equiv b\pmod n$，则$b\equiv a\pmod n$；\par
		(3) $a\equiv b\pmod n$，$b\equiv c\pmod n$，则$a\equiv c\pmod n$\par
		
	\end{Exercise}
	\jd{
		(1)设$a\pmod n={{r}_{a}},b\pmod n={{r}_{b}}$，由题意得${{r}_{a}}={{r}_{b}}$，且存在整数$j,k$，使得
		$a=jn+{{r}_{a}},b=kn+{{r}_{b}}\Rightarrow a-b=(j-k)n$，即$n|a-b$，证得$a\equiv b\pmod n$。
		\par
		(2)已知$a\equiv b\pmod n$，则存在整数$k$，使得$a=kn+b\Rightarrow b=(-k)n+a$，证得$b\equiv a\pmod n$。
		\par
		(3)已知$a\equiv b\pmod n,b\equiv c\pmod n$，则存在整数$j,k$，使得
		$a=jn+b,b=kn+c\Rightarrow a=(j+k)n+c$，证得$a\equiv c\pmod n$。
		
	}

	\begin{Exercise}
	证明以下关系\cite{yang-mcry}：\par
	(1) $[(a\pmod n)-(b\pmod n)]\pmod n=(a-b)\pmod n$；\par
	(2) $[(a\pmod n)\times (b\pmod n)]\pmod n=(a\times b)\pmod n$。
	
	\end{Exercise}
	\jd{
		(1)设$a\pmod n={{r}_{a}},b\pmod n={{r}_{b}}$，则存在整数$j,k$，使得:\\
		$
		a=jn+{{r}_{a}},b=kn+{{r}_{b}}\\
		\Rightarrow a-b=(j-k)n+({{r}_{a}}-{{r}_{b}}) \\ 
		\Rightarrow {{r}_{a}}-{{r}_{b}}=-(j-k)n+(a-b) \\ 
		\Rightarrow ({{r}_{a}}-{{r}_{b}})\pmod n=(a-b)\pmod n. \\ 
		$
		即$[(a\pmod n)-(b\pmod n)]\pmod n=(a-b)\pmod n$。
		\par
		(2)设$a\pmod n={{r}_{a}},b\pmod n={{r}_{b}}$，则存在整数$j,k$，使得\\
		$ a=jn+{{r}_{a}},b=kn+{{r}_{b}}\\
		\Rightarrow a\times b=(jkn+j{{r}_{b}}+k{{r}_{a}})n+{{r}_{a}}{{r}_{b}} \\ 
		\Rightarrow {{r}_{a}}{{r}_{b}}=-(jkn+j{{r}_{b}}+k{{r}_{a}})n+(a\times b) \\ 
		\Rightarrow ({{r}_{a}}{{r}_{b}})\pmod n=(a\times b)\pmod n. \\ 
		$
		即$[(a\pmod n)\times (b\pmod n)]\pmod n=(a\times b)\pmod n$。
		
	}


	\begin{Exercise}
		用Fermat小定理求${{3}^{201}}\pmod {11}$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为$p=11$是素数，且$\gcd (3,11)=1$，则由Fermat小定理可得：
		\[{3}^{10} \equiv 1\pmod {11}\Rightarrow {{({{3}^{10}})}^{k}}\equiv 1\pmod {11}\]
		又根据性质:
		\[ [(a\pmod n)\times (b\pmod n)]\pmod n=(a\times b)\pmod n \]
		可得：
		${{3}^{201}}\pmod {11}=[({{({{3}^{10}})}^{20}})\pmod {11})\times ({{3}^{1}}\pmod {11})]\pmod {11}=3\pmod {11}$。		
	}

	\begin{Exercise}
		用扩展Euclid算法求$67 \pmod{119}$ 的逆元。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		运算步骤如下表所示：\par
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline 
			循环次数&	Q&	X1&	X2&	X3&	Y1&	Y2&	Y3 \\ 
			\hline 
			初值&	\~{}&	1&	0&	119&	0&	1&	67  \\ 
			\hline 
			1&	1&	0&	1&	67&	1&	-1&	52  \\ 
			\hline 
			2&	1&	1&	-1&	52&	-1&	2&	15  \\ 
			\hline 
			3&	3&	-1&	2&	15&	4&	-7&	7 \\ 
			\hline 
			4&	2&	4&	-7&	7&	-9&	\textbf{\underline{16}}&	1  \\ 
			\hline 
		\end{tabular} 
	\par
	所以${{67}^{-1}}\pmod {119}=16$。
		
	}
 
 

	\begin{Exercise}
		求解下列同余方程组\cite{yang-mcry}：$\left\{ \begin{matrix}
		x\equiv 2\pmod 3  \\
		x\equiv 1\pmod 5  \\
		x\equiv 1\pmod 7  \\
		\end{matrix} \right.$
	\end{Exercise}
	\jd{
		根据中国剩余定理求解该同余方程组，记${{a}_{1}}=2,{{a}_{2}}=1,{{a}_{3}}=1{{m}_{1}}=3,{{m}_{2}}=5,{{m}_{3}}=7$，$M={{m}_{1}}\times {{m}_{2}}\times {{m}_{3}}\text{=}105$，则有:\par
		\[ {{M}_{1}}=\frac{M}{{{m}_{1}}}=35,M_{1}^{-1}\pmod {{m}_{1}}={{35}^{-1}}\pmod 3=2\]
		\[ {{M}_{2}}=\frac{M}{{{m}_{2}}}=21,M_{2}^{-1}\pmod {{m}_{2}}={{21}^{-1}}\pmod 5=1 \]
		\[ {{M}_{3}}=\frac{M}{{{m}_{3}}}=15,M_{3}^{-1}\pmod {{m}_{3}}={{15}^{-1}}\pmod 7=1 \]
	
		\par
		所以方程组的解为:\par
		$
		 x\equiv ({{M}_{1}}M_{1}^{-1}{{a}_{1}}+{{M}_{2}}M_{2}^{-1}{{a}_{2}}+{{M}_{3}}M_{3}^{-1}{{a}_{3}})\pmod M \\
		 \equiv (35\times 2\times 2+21\times 1\times 1+15\times 1\times 1)\pmod 105 \\ 
		 \equiv 176\pmod 105\equiv 71\pmod 105. \\ 
		$
		
	}


	 \begin{Exercise}
	 	证明：群G是交换群的充要条件是对任意的$a,b \in G$，有$(ab)^2 =a^2b^2$。
	 	\cite{mooc现代密码学聂旭云}
	 \end{Exercise}
	 \jd{
	 	必要性：若G是交换群，则对任意$a,b\in G$，有$ab=ba$，从而$(ab)^2=abab=aabb=a^2b^2$.\par
	 	充分性：若对任意$a,b \in G$,有$(ab)^2=a^2b^2$,那么$ba=ebae=a^{-1}ababb^{-1}=a^{-1}(ab)^2b^{-1}=a^{-1}ababb^{-1}=ebae=ba$.
	 }

	\begin{Exercise}
		证明当且仅当$n$是素数时，$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$是域。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)若$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$是域，则$<{{Z}_{n}},{{+}_{n}}>$，$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$均为Abel群。显然$<{{Z}_{n}},{{+}_{n}}>$为Abel群，与n是否为素数无关；但若$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$为Abel群，其条件之一必须保证对任意$x\in {{Z}_{n}}-\{\text{0}\}$有模乘法逆元，即对任意$x\in {{Z}_{n}}-\{\text{0}\}$，有$y\in {{Z}_{n}}-\{\text{0}\}$，使得$x\times y\equiv \text{1}\pmod n$，所以$\gcd (x,n)=1$，即$\varphi (n)=n-1$，$n$为素数。
		\par
		(2)若$n$不是素数，则$\varphi (n)<n-1$，即至少存在一个$x\in {{Z}_{n}}-\{\text{0}\}$，使得$\gcd (x,n)\ne \text{1}$，即$x$无模乘法逆元，因此不能保证$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$均为Abel群，即$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$不是域。	
	}

\chapter{公钥密码体制}
 
	\begin{Exercise}
		设通信双方使用RSA加密体制，接收方的公开钥是$(e,n)=(5,35)$，接收到的密文是$C=10$，求明文$M$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为$n=35=5\times 7\Rightarrow p=5,q=7$，则$\varphi (n)=(p-1)\left( q-1 \right)=4\times 6=24$，所以
		$d\equiv {{e}^{-1}}\bmod \varphi (n)\equiv {{5}^{-1}}\bmod 24\equiv 5\bmod 24$，即明文$M\equiv {{C}^{d}}\bmod n\equiv {{10}^{5}}\bmod 35\equiv 5$。
		
	}

 

	\begin{Exercise}
		设RSA加密体制的公开钥是$(e,n)=(77,221)$。\par
		(1) 用重复平方法加密明文$160$，得中间结果为：
		\begin{center}
			${{160}^{2}}(\bmod {221})\equiv 185$ \\ 
			$ {{160}^{4}}(\bmod {221})\equiv 191$ \\ 
			$ {{160}^{8}}(\bmod {221})\equiv 16$ \\ 
			$ {{160}^{16}}(\bmod {221})\equiv 35$ \\ 
			$ {{160}^{32}}(\bmod {221})\equiv 120$ \\ 
			$ {{160}^{64}}(\bmod {221})\equiv 35$ \\ 
			$ {{160}^{72}}(\bmod {221})\equiv 118$ \\ 
			$ {{160}^{76}}(\bmod {221})\equiv 217$ \\ 
			$ {{160}^{77}}(\bmod {221})\equiv 23$ \\ 
		\end{center}
		\par
		若敌手得到以上中间结果就很容易分解$n$，问敌手如何分解$n$。\par
		(2) 求解密密钥d。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)由以上中间结果可得：\\
		$
		 {{160}^{16}}(\bmod 221)\equiv 35\equiv {{160}^{64}}(\bmod 221) \\ 
		 \Rightarrow {{160}^{64}}-{{160}^{16}}\equiv 0(\bmod 221) \\ 
		 \Rightarrow ({{160}^{32}}-{{160}^{8}})({{160}^{32}}+{{160}^{8}})\equiv 0(\bmod 221) \\ 
		 \Rightarrow (120-16)(120+16)\equiv 0(\bmod 221) \\ 
		 \Rightarrow 104\times 136\equiv 0(\bmod 221) \\ 
		$\par
		由$\gcd (104,221)=13,\gcd (136,221)=17$，可知分解为$221=13\times 17$。
		\par
		(2)解密密钥$d={{e}^{-1}}\bmod (\varphi (n))={{77}^{-1}}\bmod (\varphi (13\times 17))={{77}^{-1}}\bmod (12\times 16)$，由扩展的Eucild算法可得$d=5$。
	}
 
 	\begin{Exercise}
 		在Elgamal加密体制中:\par
 		(1) Alice和Bob使用p=17和g=3，Bob选择x=6做为他的私钥，试确定Bob的公钥。\par
 		(2) 当Alice取随机数k=10，试确定明文m=6的密文，并给出正确的解密过程。
 		\cite{mooc现代密码学聂旭云}
 	\end{Exercise}
 	\jd{
 		Bob的私钥$y=g^x \pmod {p}=3^6 \pmod {17}=15$。\par
 		明文m=6的密文$C_1 = g^k \pmod {p}=3^{10} \pmod{17}=8$\par
 		$C_2 = y^k \pmod {p}= 15^{10} \cdot 6 \pmod {17}=7$\par
 		解密过程为$m=C_2/C_1^x \pmod {p} = 15/8^6 \pmod {17} =7 \cdot 13 \pmod {17} =6$
 	}
 
 	
	\begin{Exercise}
		在ElGamal加密体制中，设素数$p=71$，本原根$g=7$:\par
		(1) 如果接收方B的公开钥是${{y}_{B}}=3$，发送方A选择的随机整数$k=2$，求明文$M=30$所对应的密文。\par
		(2) 如果A选择另一个随机整数$k$，使得明文$M=30$加密后的密文是$C=(59,{{C}_{2}})$，求${{C}_{2}}$。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)密文$C=({{C}_{1}},{{C}_{2}})$，其中：
		${{C}_{1}}={{g}^{k}}\bmod p={{7}^{2}}\bmod 71=49,{{C}_{2}}=({{y}_{B}}^{k}M)\bmod p=({{3}^{2}}\times 30)\bmod 71=57$。
		所以明文$M=30$对应的密文为$C=(49,57)$。\par
		(2)由${{C}_{1}}={{g}^{k}}\bmod p\Rightarrow 59={{7}^{k}}\bmod 71$，穷举法可得$k=3$。
		所以${{C}_{2}}=({{y}_{B}}^{k}M)\bmod p=({{3}^{3}}\times 30)\bmod 71=29$。
	}

 
	\begin{Exercise}
		设背包密码系统的超递增序列为$(3,4,9,17,35)$，乘数$t=19$，模数$k=73$，试对good night加密\cite{yang-mcry}。字符编码表如下：\par
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
			\hline 
			字母&序号  & 二进制 & 字母 & 序号 & 二进制 & 字母 & 序号 & 二进制 \\ 
			\hline 
			(空格)& 0 &00000  & I & 9 & 01001 & R &18  & 10010 \\ 
			\hline 
			A& 1 & 00001 & J & 10 & 01010 & S &19  & 10011 \\ 
			\hline 
			B& 2 & 00010 & K &11  & 01011 &T  & 20 & 10100 \\ 
			\hline 
			C& 3 & 00011 & L &12  & 01100 &U  & 21 & 10101 \\ 
			\hline 
			D& 4 & 00100 & M & 13 & 01101 & V & 22 & 10110 \\ 
			\hline 
			E& 5 & 00101 & N & 14 &01110  & W & 23 & 10111 \\ 
			\hline 
			F& 6 & 00110 & O & 15 & 01111 & X & 24 & 11000 \\ 
			\hline 
			G&7  & 00111 & P & 16 & 10000 & Y & 25 & 11001 \\ 
			\hline 
			H&8  & 01000 & Q & 17 & 10001 & Z &26  & 11010 \\ 
			\hline 
		\end{tabular} 
		\par
	\end{Exercise}
	\jd{
		由$A=(3,4,9,17,35)$，乘数$t=19$，模数$k=73$，可得$B=t\times A\bmod k=(57,3,25,31,8)$。
		明文“good night”的编码为“00111”，“01111”，“01111”，“00100”，“00000”，“01110”，“01001”，“00111”，“01000”，“10100”，则有：\\
		$
		 f(00111)=25+31+8=64, \\ 
		 f(01111)=3+25+31+8=67, \\ 
		 f(01111)=3+25+31+8=67, \\ 
		 f(00100)=25, \\ 
		 f(00000)=0, \\ 
		 f(01110)=3+25+31=59, \\ 
		 f(01001)=3+8=11, \\ 
		 f(00111)=25+31+8=64, \\ 
		 f(01000)=3, \\ 
		 f(10100)=57+25=82=9\bmod 73. \\ 
		$
		所以明文“good night”相应的密文为$(64,67,67,25,0,59,11,64,3,9)$。
	}

 
	\begin{Exercise}
		设背包密码系统的超递增序列为$(3,4,8,17,35)$，乘数$t=17$，模数$k=67$，试对$24,2,72,110$解密。字符编码表如下：\par
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
			\hline 
			字母&序号  & 二进制 & 字母 & 序号 & 二进制 & 字母 & 序号 & 二进制 \\ 
			\hline 
			(空格)& 0 &00000  & I & 9 & 01001 & R &18  & 10010 \\ 
			\hline 
			A& 1 & 00001 & J & 10 & 01010 & S &19  & 10011 \\ 
			\hline 
			B& 2 & 00010 & K &11  & 01011 &T  & 20 & 10100 \\ 
			\hline 
			C& 3 & 00011 & L &12  & 01100 &U  & 21 & 10101 \\ 
			\hline 
			D& 4 & 00100 & M & 13 & 01101 & V & 22 & 10110 \\ 
			\hline 
			E& 5 & 00101 & N & 14 &01110  & W & 23 & 10111 \\ 
			\hline 
			F& 6 & 00110 & O & 15 & 01111 & X & 24 & 11000 \\ 
			\hline 
			G&7  & 00111 & P & 16 & 10000 & Y & 25 & 11001 \\ 
			\hline 
			H&8  & 01000 & Q & 17 & 10001 & Z &26  & 11010 \\ 
			\hline 
		\end{tabular} 
	\par
	\end{Exercise}
	\jd{
		${{t}^{-1}}\bmod k={{17}^{-1}}\bmod 67=4\bmod 67$,所以私钥为$\left\lbrace(4,67) \right\rbrace$，或$\left\lbrace((3,4,8,17,35),4,67) \right\rbrace$ 。\par
		$17\times (3 4 8 17 35) \pmod{67}=(51 1 2 21 59)$，所以公钥为$\left\lbrace((51,1,2,21,59),67) \right\rbrace$。 \par
		下面根据私钥进行解密：\par
		$4\times (24,2,72,110)\bmod 67=(29,8,20,38)$。\par
		所以其对应的明文分组为$(01110,00100,10010,10001)$，查表可得明文为"NDRQ"。
	}

 
 
	\begin{Exercise}
		在Rabin密码体制中设$p=53,q=59$： \par
		(1) 确定$1$在模$n$下的4个平方根。\par
		(2) 求明文消息$2347$所对应的密文。\par
		(3) 对上述密文，确定可能的4个明文。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)已知 $n=pq=53\times 59=3125$，由中国剩余定理可得到等价方程组：\par
		$\left\{ 
		 {{x}^{2}}\equiv 1\bmod 53 \\ 
		 {{x}^{2}}\equiv 1\bmod 59 \\ 
		 \right.$
		因为${{(\pm 1)}^{2}}\equiv 1\bmod 53{{(\pm 1)}^{2}}\equiv 1\bmod 59$，所以$x\equiv \pm 1\bmod 53x\equiv \pm 1\bmod 59$。经组合可得到以下四个方程组：\par
		\begin{equation}
			\begin{cases} 
				x\equiv 1\bmod 53 \\ 
				x\equiv 1\bmod 59 
			\end{cases} 
		\end{equation}
		\begin{equation}
			\begin{cases}
				x\equiv 1\bmod 53 \\ 
				x\equiv -1\bmod 59  
			\end{cases} 
		\end{equation}
		\begin{equation}	
			\begin{cases}
				x\equiv -1\bmod 53 \\ 
				x\equiv 1\bmod 59 
			\end{cases} 
		\end{equation}
		\begin{equation}
			\begin{cases} 
				x\equiv -1\bmod 53 \\ 
				x\equiv -1\bmod 59 
			\end{cases} 
		\end{equation}
		
		 \par
		根据中国剩余定理${{M}_{1}}=59,M_{1}^{-1}\bmod 53\equiv 9,{{M}_{2}}=53,M_{2}^{-1}\bmod 59\equiv 49$，则有：\\
		第一个方程组的解为$(59\cdot 9\cdot 1+53\cdot 49\cdot 1)\bmod 3127\equiv 1$；\\
		第二个方程组的解为$(59\cdot 9\cdot 1+53\cdot 49\cdot (-1))\bmod 3127\equiv 1061$；\\
		第三个方程组的解为$(59\cdot 9\cdot (-1)+53\cdot 49\cdot 1)\bmod 3127\equiv 2066$；\\
		第四个方程组的解为$(59\cdot 9\cdot (-1)+53\cdot 49\cdot (-1))\bmod 3127\equiv 3126$。\\
		所以，$1\bmod n$的四个平方根为$1\bmod n1061\bmod n2066\bmod n3126\bmod n$。\par
		
		(2)$2347$对应的密文为$c\equiv {{2347}^{2}}\bmod 3127\equiv 1762$。\par
		
		(3)解密即解${{x}^{2}}\equiv 1762\bmod 3127$，由中国剩余定理可得到等价方程组：\par
		$\left\{ 
		 {{x}^{2}}\equiv 1762\bmod 53=13 \\ 
		 {{x}^{2}}\equiv 1762\bmod 59=51 \\ 
		 \right.$
		 \par
		因为${{(\pm 15)}^{2}}\equiv 13\bmod 53{{(\pm 13)}^{2}}\equiv 51\bmod 59$，所以$x\equiv \pm 15\bmod 53,x\equiv \pm 13\bmod 59$，经组合可得到以下四个方程组：\par
		$\left\{ 
		 x\equiv 15\bmod 53 \\ 
		 x\equiv 13\bmod 59 \\ 
		 \right.$	$\left\{ 
		 x\equiv 15\bmod 53 \\ 
		 x\equiv -13\bmod 59 \\ 
		 \right.$ $\left\{ 
		 x\equiv -15\bmod 53 \\ 
		 x\equiv 13\bmod 59 \\ 
		 \right.$ $\left\{ 
		 x\equiv -15\bmod 53 \\ 
		 x\equiv -13\bmod 59 \\ 
		 \right.$
		 \par
		根据中国剩余定理${{M}_{1}}=59,{{M}_{1}}^{-1}\bmod 53\equiv 9,{{M}_{2}}=53,M_{2}^{-1}\bmod 59\equiv 49$，则有：\\
		第一个方程组的解为$(59\cdot 9\cdot 15+53\cdot 49\cdot 13)\bmod 3127\equiv 1075$；\\
		第二个方程组的解为$(59\cdot 9\cdot 15+53\cdot 49\cdot (-13))\bmod 3127\equiv 2347$；\\
		第三个方程组的解为$(59\cdot 9\cdot (-15)+53\cdot 49\cdot 13)\bmod 3127\equiv 780$；\\
		第四个方程组的解为$(59\cdot 9\cdot (-15)+53\cdot 49\cdot (-13))\bmod 3127\equiv 2052$。\\
		所以，四个可能的明文为$1075,2347,780,2052$。\
	}

 
	\begin{Exercise}
		椭圆曲线${{E}_{11}}(1,6)$表示${{y}^{2}}\equiv {{x}^{3}}+x+6\pmod{11}$，求其上的所有点。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		模$11$的平方剩余有$1,4,9,5,3$。\\
		$x=1,4,6$时，${{y}^{2}}\equiv 8\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=9$时，${{y}^{2}}\equiv 7\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=0$时，${{y}^{2}}\equiv 6\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=2$时，${{y}^{2}}\equiv 2\bmod 11,y=47$；\\
		$x=\text{3}$时，${{y}^{2}}\equiv 3\bmod 11,y=5\text{6}$；\\
		$x=\text{5}\text{7}\text{10}$时，${{y}^{2}}\equiv 4\bmod 11y=2\text{9}$；\\
		$x=\text{8}$时，${{y}^{2}}\equiv 9\bmod 11,y=3\text{8}$。\par
		所以椭圆曲线${{E}_{11}}(1,6)$上的所有点为：\\
		$\left\lbrace  (2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),O\right\rbrace $。
	}

 
	\begin{Exercise}
		已知点$G=(2,7)$在椭圆曲线${{E}_{11}}(1,6)$上，求$2G$和$3G$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)求$2G$。\\
		$
		 \lambda =\frac{3\times {{2}^{2}}+1}{2\times 7}\bmod 11=(13\times 4)\bmod 11=8\bmod 11, \\ 
		 {{x}_{2G}}=({{8}^{2}}-2-2)\bmod 11=5\bmod 11, \\ 
		 {{y}_{2G}}=[8\times (2-5)-7]\bmod 11=8\bmod 11, \\ 
		$\par
		所以$2G=(5,2)$。
		\par
		(2)易知$3G=2G+G=(5,2)+(2,7)$。\\
		$
		 \lambda =\frac{7-2}{5-2}\bmod 11=(5\times 7)\bmod 11=2\bmod 11, \\ 
		 {{x}_{3G}}=({{2}^{2}}-5-2)\bmod 11=8\bmod 11, \\ 
		 {{y}_{3G}}=[2\times (5-8)-2]\bmod 11=3\bmod 11, \\ 
		$
		\par
		所以$3G=(8,3)$。
	}


	\begin{Exercise}
		利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是${{E}_{11}}(1,6)$，生成元$G=(2,7)$，接收方A的秘密钥${{n}_{A}}=7$。\par
		(1) 求A的公开钥${{P}_{A}}$。\par
		(2) 发送方B欲发送消息${{P}_{m}}=(10,9)$，选择随机数$k=3$，求密文${{C}_{m}}$。\par
		(3) 显示接收方A从密文${{C}_{m}}$恢复消息${{P}_{m}}$的过程。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)易知公开钥${{P}_{A}}=7G=2\times 2G+3G$。\par
		$\bullet$求$2\times 2G$。\\
		$
		 \lambda =\frac{3\times {{5}^{2}}+1}{2\times 2}\bmod 11=(10\times 3)\bmod 11=8\bmod 11, \\ 
		 {{x}_{4G}}=({{8}^{2}}-5-5)\bmod 11=10\bmod 11, \\ 
		 {{y}_{4G}}=[8\times (5-10)-2]\bmod 11=2\bmod 11, \\ 
		$\par
		所以$2\times 2G=(10,2)$。
		\par
		$\bullet$由题19可得$3G=(8,3)$，即${{P}_{A}}=2\times 2G+3G=(10,2)+(8,3)$。\\
		$
		 \lambda =\frac{3-2}{8-10}\bmod 11=(1\times 5)\bmod 11=5\bmod 11, \\ 
		 {{x}_{7G}}=({{5}^{2}}-10-8)\bmod 11=7\bmod 11, \\ 
		 {{y}_{7G}}=[5\times (10-7)-2]\bmod 11=2\bmod 11, \\ 
		$\par
		所以${{P}_{A}}=(7,2)$。
		\par
		\par
		
		(2)密文${{C}_{m}}=(kG,{{P}_{m}}+k{{P}_{A}})$。
		$\bullet$求$kG$：$kG=3G=(8,3)$。
		\par
		$\bullet$求$k{{P}_{A}}$：$k{{P}_{A}}=2{{P}_{A}}+{{P}_{A}}=3G+7G=(2,7)+(7,2)$。
		$
		 \lambda =\frac{2-7}{7-2}\bmod 11=-1\bmod 11, \\ 
		 {{x}_{3{{P}_{A}}}}=({{(-1)}^{2}}-2-7)\bmod 11=3\bmod 11, \\ 
		 {{y}_{3{{P}_{A}}}}=((-1)\times (2-3)-7)\bmod 11=5\bmod 11, \\ 
		$
		所以$k{{P}_{A}}=(3,5)$。
		\par
		$\bullet$求${{P}_{m}}+k{{P}_{A}}$：${{P}_{m}}+k{{P}_{A}}=(10,9)+(3,5)$。
		$\
		 \lambda =\frac{5-9}{3-10}\bmod 11=-1\bmod 11, \\ 
		 {{x}_{{{P}_{m}}+k{{P}_{A}}}}=({{(-1)}^{2}}-10-3)\bmod 11=10\bmod 11, \\ 
		 {{y}_{{{P}_{m}}+k{{P}_{A}}}}=((-1)\times (10-10)-9)\bmod 11=2\bmod 11, \\ 
		$
		所以${{P}_{m}}+k{{P}_{A}}=(10,2)$。\par
		综上：${{C}_{m}}=(kG,{{P}_{m}}+k{{P}_{A}})=\{(8,3),(10,2)\}$。\par
		\par
		\par
		(3)从密文${{C}_{m}}$恢复消息${{P}_{m}}$的过程如下：\\
		$
		 {{P}_{m}}=({{P}_{m}}+k{{P}_{A}})-{{n}_{A}}(kG) \\ 
		 =(10,2)-7(8,3) \\ 
		 =(10,2)-(3,5) \\ 
		 =(10,2)+(3,6) \\ 
		 =(10,9). \\ 
		$\par
		其中：\\
		a)计算$7(8,3)$\\
		$\bullet$先计算$2(8,3)$。\\
		$
		 \lambda =\frac{3\times {{8}^{2}}+1}{2\times 3}\equiv 1\bmod 11, \\ 
		 {{x}_{2(8,3)}}={{1}^{2}}-8-8\equiv 7\bmod 11, \\ 
		 {{y}_{2(8,3)}}=1(8-7)-3\equiv 9\bmod 11, \\ 
		$\\
		所以$2(8,3)=(7,9)$。
		\\
		$\bullet$计算$3(8,3)=2(8,3)+(8,3)$。\\
		$
		 \lambda =\frac{3-9}{8-7}\equiv 5\bmod 11, \\ 
		 {{x}_{3(8,3)}}={{5}^{2}}-7-8\equiv 10\bmod 11, \\ 
		 {{y}_{3(8,3)}}=5(7-10)-9\equiv 9\bmod 11, \\ 
		$\\
		所以$3(8,3)=(10,9)$。
		\\
		$\bullet$计算$6(8,3)=3(8,3)+3(8,3)$。\\
		$
		 \lambda =\frac{3\times {{10}^{2}}+1}{2\times 9}=\frac{301}{18}\equiv 10\bmod 11, \\ 
		 {{x}_{6(8,3)}}={{10}^{2}}-10-10\equiv 3\bmod 11, \\ 
		 {{y}_{6(8,3)}}=10(10-3)-9\equiv 6\bmod 11, \\ 
		$\\
		所以$6(8,3)=(3,6)$。
		\\
		$\bullet$计算$7(8,3)=6(8,3)+(8,3)$。\\
		$
		 \lambda =\frac{3-6}{8-3}=\frac{-3}{5}\equiv 6\bmod 11, \\ 
		 {{x}_{7(8,3)}}={{6}^{2}}-3-8\equiv 3\bmod 11, \\ 
		 {{y}_{7(8,3)}}=6(3-3)-6\equiv 5\bmod 11, \\ 
		$\\
		所以$7(8,3)=(3,5)$。
		\\
		b)计算$\left( 10,2\right)-7\left( 8,3\right) = \left( 10,2\right)-\left( 3,5\right) =\left( 10,2\right)+\left( 3,-5\right) = \left( 10,2\right)+\left( 3,6\right) $ 。\\
		$
		 \lambda =\frac{6-2}{3-10}=\frac{4}{-7}\equiv 1\bmod 11, \\ 
		 x_{P_m}={{1}^{2}}-10-3\equiv 10\bmod 11, \\ 
		 {{y}_{{{P}_{m}}}}=1(10-10)-2\equiv 9\bmod 11, \\ 
		$\\
		所以$(10,2)-7(8,3)=(10,9)$。
		
	}

\chapter{密钥分配与管理}

	
	\begin{Exercise}
		在公钥体制中，每一用户U都有自己的公开钥$P{{K}_{U}}$和秘密钥$S{{K}_{U}}$。如果任意两个用户A,B按以下方式通信，A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$，B收到后，自动向A返回消息$\left( {{E}_{P{{K}_{A}}}}\left( \text{m} \right),B \right)$，以使A知道B确实收到报文m。\par
		（1）问用户C怎样通过攻击手段获取报文m？\par
		（2）若通信格式变为：\par
		$\bullet$ A发给B消息${{E}_{P{{K}_{B}}}}\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$\par
		$\bullet$ B向A返回消息${{E}_{P{{K}_{A}}}}\left( {{E}_{S{{K}_{_{B}}}}}\left( m \right),m,B \right)$\par
		这时的安全性如何？分析这时A、B如何相互认证并传递消息m。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)当A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$时，A的身份“A”并没有认证，而B在收到消息后也无法对发送者进行检验，且身份A，B均明文传输，因此用户C可通过如下手段获得报文m：
		当A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$时，C截取该消息并将身份A替换为自己的身份C，将修改后的消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),C \right)$发给接收者B；
		B提取消息后，根据身份“C”将返回消息$\left( {{E}_{P{{K}_{C}}}}\left( \text{m} \right),B \right)$；
		C再次劫取B返回的消息$\left( {{E}_{P{{K}_{C}}}}\left( \text{m} \right),B \right)$，用自己的私钥$S{{K}_{C}}$解密出消息m，并用A的公钥对m加密后将消息$\left( {{E}_{P{{K}_{A}}}}\left( \text{m} \right),B \right)$发给A。
		这样，用户C获得了报文m而没有影响A,B之间的正常通信，实现了攻击。
		\par
		
		(2)根据消息格式，先对消息m进行了签名，然后再进行加密，传送的消息具有了保密性和认证性，敌手无法获得报文明文，安全性提高。
		A，B之间相互认证传递消息的过程如下：
		B收到消息${{E}_{P{{K}_{B}}}}\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$时，先用B自己的私钥解密得到消息$\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$，然后根据提取的身份信息A，用A的公钥对消息m的签名${{E}_{S{{K}_{A}}}}\left( m \right)$的正确性进行验证，如果验证通过，则说明消息确实来自A。反之A用相同的方法可验证${{E}_{P{{K}_{A}}}}\left( {{E}_{S{{K}_{_{B}}}}}\left( m \right),m,B \right)$确实来自B，从而实现了相互认证。
	}

	\begin{Exercise}
		Diffie-Hellman密钥交换协议易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥。详细分析攻击者如何实施攻击。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		虽然Diffie-Hellman密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。当Alice和Bob交换数据时，Trudy 拦截通信信息，并冒充Alice欺骗Bob，冒充Bob欺骗Alice。其过程如下：\\
		（1）Alice选取大的随机数x，并计算$X={{g}^{x}}\left( \bmod P \right)$，Alice将g、P、X传送给Bob，但被Trudy拦截；\\
		（2）Trudy冒充Alice选取大的随机数z，并计算$Z={{g}^{z}}\left( \bmod P \right)$，Trudy将Z传送给Bob；\\
		（3）Trudy冒充Bob，再将$Z={{g}^{z}}\left( \bmod P \right)$传送给Alice；\\
		（4）Bob选取大的随机数y，并计算$Y={{g}^{y}}\left( \bmod P \right)$，Bob将Y传送给Alice，但被Trudy拦截。\par
		由（1）、（3）Alice与 Trudy 共享了一个秘密密钥${{g}^{xz}}$，由（2）、（4）Trudy与Bob共享了一个秘密密钥${{g}^{yz}}$。
		以后在通信过程中，只要Trudy作中间人，Alice和 Bob不会发现通信的异常，但 Trudy可以获取所有通信内容。
		
	}

	\begin{Exercise}
		Diffie-Hellman密钥交换过程中，设大素数p=11，a=2是p的本原根.\par
		（1）用户A的公开钥${{Y}_{A}}\text{=}9$，求其秘密钥${{X}_{A}}$。\par
		（2）设用户B的公开钥${{Y}_{B}}=3$，求A和B的共享密钥K。		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)${{X}_{A}}$满足${{Y}_{A}}={{a}^{{{X}_{A}}}}\bmod p$即$9\text{=}{{2}^{{{X}_{A}}}}\bmod 11$，所以有${{X}_{A}}$=6。\par
		(2)由Diffie-Hellman协议可知$K\text{=}Y_{B}^{{{X}_{A}}}\bmod p={{3}^{6}}\bmod 11=3$。
	}


	\begin{Exercise}
		在Shamir秘密分割门限方案中，设k=3，n=5，q=17，5个子密钥分别是8、7、10、0、11，从中任选3个，构造插值多项式并求秘密数据s。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		取$f\left( 1 \right)=8$，$f\left( 2 \right)=7$，$f\left( 4 \right)=0$构造插值多项式:\\
		$
		f\left( x \right)=8\dfrac{\left( x-2 \right)\left( x-4 \right)}{\left( 1-2 \right)\left( 1-4 \right)}
		+7\dfrac{\left( x-1 \right)\left( x-4 \right)}{\left( 2-1 \right)\left( 2-4 \right)} 
		+0\dfrac{\left( x-1 \right)\left( x-2 \right)}{\left( 4-1 \right)\left( 4-2 \right)} 
		$ \\
		$				
		=8\dfrac{\left( x-2 \right)\left( x-4 \right)}{3}+7\dfrac{\left( x-1 \right)\left( x-4 \right)}{-2}\bmod 17 \\ 
		=8 (3)^{-1} \left( x-2 \right)\left( x-4 \right) +7 (-2)^{-1} \left( x-1 \right)\left( x-4 \right) \pmod{17}\\ 
		=8\times 6 \left( x-2 \right)\left( x-4 \right) +7 \times 8 \left( x-1 \right)\left( x-4 \right) \pmod{17}\\
		=14(x^2-6x+8)+5(x^2-5x+4)\pmod{17}\\
		=14x^2+x+10+5x^2+9x+3 \pmod{17}\\
		=19x^2+10x+13 \pmod{17}\\
		=2x^2+10x+13
		$\\
		
		$s=f\left( 0 \right)=13$
		
	}

	\begin{Exercise}
		在基于中国剩余定理的秘密分割门限方案中，设$k=2$，$n=3$，${{m}_{1}}=7$，${{m}_{2}}=9$，${{m}_{3}}=11$，三个子秘钥分别是6、3、4，求秘密数据s。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由题设可得s应满足$11={{m}_{3}}<s<{{m}_{1}}{{m}_{2}}=63$,
		因为$k=2，n=，{{m}_{1}}=7，{{m}_{2}}=9，{{m}_{3}}=11$，3个子密钥分别是6，3，4，那么:\\
		$
		M={{m}_{1}}\times {{m}_{2}}\times {{m}_{3}}\\
		=7\times 9\times 11\\
		=693 {{M}_{1}}\\
		=\frac{M}{{{m}_{1}}}
		=\frac{693}{7}=99$，\\
		
		${{N}_{1}}={{M}_{1}}^{-1}(\bmod {{m}_{1}})\\
		=9{{9}^{-1}}\bmod 7=1$\\
		
		${{M}_{2}}=\frac{M}{{{m}_{2}}}\\
		=\frac{693}{9}=77，\\
		{{N}_{2}}={{M}_{2}}^{-\text{1}}(\bmod {{m}_{2}})=7{{7}^{-1}}\bmod 9=2$\\
		
		${{M}_{3}}=\frac{M}{{{m}_{3}}}=\frac{693}{11}=63，{{N}_{3}}={{M}_{3}}^{-1}(\bmod {{m}_{3}})=6{{3}^{-1}}\bmod 11=7$
		\\
		由${{s}_{1}}=6，{{s}_{2}}=3$ 可得:\\
		$s={{s}_{1}}{{M}_{1}}{{N}_{1}}+{{s}_{2}}{{M}_{2}}{{N}_{2}}(\bmod 63)\\
		=6\times 99\times 1+3\times 77\times 2(\bmod 63)\\
		=1056(\bmod 63)\\
		=48$
		\\
		由${{s}_{2}}=3$，${{s}_{3}}=4$可得:\\
		$s={{s}_{2}}{{M}_{2}}{{N}_{2}}+{{s}_{3}}{{M}_{3}}{{N}_{3}}(\bmod 99)\\
		=3\times 77\times 2+4\times 63\times 7(\bmod 99)\\
		=2226(\bmod 99)\\
		=48$
		\\
		由${{s}_{1}}=6$，${{s}_{3}}=4$可得:\\
		$s={{s}_{1}}{{M}_{1}}{{N}_{1}}+{{s}_{3}}{{M}_{3}}{{N}_{3}}(\bmod 77)\\
		=6\times 99\times 1+4\times 63\times 7(\bmod 77)\\
		=2358(\bmod 77)\\
		=48$
		即秘密数据s为48.
	}

\chapter{消息认证和哈希函数}
	\begin{Exercise}
		消息认证能提供的安全属性有哪些？
	\end{Exercise}
	\jd{
		消息认证是一个过程，用于验证接收消息的真实性(确定消息是否真的是从声称方发来的)和完整性(消息是否被篡改、插入和删除)，同时还用于验证消息的顺序性和时间性(未被重排、重放、延迟)。
	}

	\begin{Exercise}
		利用DES的CBC模式进行消息认证(如\ref{fig:MAC-DES-CBC}所示)，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。
		\cite{yang-mcry}
	\end{Exercise}
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.6\linewidth] {MAC-DES-CBC.png}
		\caption{DES的CBC模式进行消息认证}
		\label{fig:MAC-DES-CBC}
	\end{figure}

	\jd{
		用CBC模式的DES设计数据认证算法为：\par
		\begin{align}
			&O_1=E_K(D_1) \\
			&O_2 = E_K(D_2 \oplus O_1)\\
			&O_3 = E_K(D_3 \oplus O_2)\\
			&\Rightarrow O_N=E_K(D_N \oplus E_K(D_{N-1}\oplus\ldots \oplus E_K(D_2 \oplus E_K(D_1))))\\
			&\cdots\\
			&O_N = E_K(D_N \oplus O_{N-1})\nonumber
		\end{align}

		\par
		如果改用CFB模式来实现，由于输出为64位，所以必须取$j=64$ ，也就是每次移位寄存器左移整个64位。为了达到相同的结果，可取CFB模式中$IV=D_1,P_i=D_{i+1},P_N=0 \left( i=1,\ldots,N-1 \right) $ ，则有：\\
		\begin{align}
			&O_1=D_2 \oplus E_K(D_1) \\
			&O_2 = D_3 \oplus E_K( O_1)\\
			&O_3 = D_4 \oplus E_K( O_2)\\
			&\Rightarrow O_N=E_K(O_{N-1})=E_K(D_N \oplus E_K(D_{N-1}\oplus\ldots \oplus E_K(D_2 \oplus E_K(D_1))))\\
			&\cdots\\
			&O_{N-1} = D_N \oplus E_K(O_{N-2})\\
			&O_N = 0 \oplus E_K(O_{N-1}) \nonumber
		\end{align}
		比较两式， $O_N$作为消息认证码，结果相同。
		
	}

	
	\begin{Exercise}
		什么是哈希函数的抗强碰撞性？抗弱碰撞性？单向性？
	\end{Exercise}
	\jd{找到任意两个不同输入$y,x,y \neq x$,满足$h(y)=h(x)$在计算上是不可行的，称为此哈希函数具有抗强碰撞性。\par
		已知x，找到$y,y \neq x,$满足$h(y)=h(x)$，在计算上是不可行的，称为此哈希函数具有抗弱碰撞性。\par
		已知y，找到x满足$y=h(x)$在计算上不可行，称为哈希函数的单向性。
	}

	\begin{Exercise}
		以下Hash函数的输入分组长度和输出数据长度分别为多少。\par
		\begin{enumerate}
			\item MD5
			\item SHA1
			\item SM3
		\end{enumerate}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item MD5:算法输入为任意长的消息，分割为512比特长的分组，输出为128比特的消息摘要。
			\item SHA1:算法输入为小于$2^{64}$比特长的任意消息，分割为512比特长的分组，输出160比特长的摘要消息。
			\item SM3:算法输入为$l(1\leq l \leq 2^{64}-1)$比特，分割为512比特长的分组，输出256比特长的摘要消息。
		\end{enumerate}
	}

	\begin{Exercise}
		有很多哈希函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组$M_1, M_2,…,M_N，H_0=$初值，迭代关系为 $H_i=E_{M_i}\left( H_{i-1}\right) \oplus H_{i-1}\left( i=1,2,…,N\right) $,哈希值取为$H_N$，其中E是分组加密算法。\par
		（1）设E为DES，我们在前面的习题已证明如果对明文分组和加密密钥都逐比特取补，那么得到的密文也
		是原密文的逐比特取补，即如果$Y=DES_K\left( X\right) $，那么$Y’=DES_{K’}\left( X’\right) $。利用这一结论证明在上述哈希函数中可对消息进行修改但却保持哈希值不变。\par
		（2）若迭代关系$H_i=E_{H_{i-1}} \left(M_i \right) \oplus M_i$ ，证明仍可对其进行上述攻击。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)敌手主要是通过修改函数的输入值 $M_1,M-2,\ldots,M_N$和 来构造碰撞。\par
		\begin{align}
			&H_1=DES_{M_1}\left(H_0 \right) \oplus H_0\\
			&H_2=DES_{M_2}\left(H_1 \right) \oplus H_1\\
			&\ldots \\
			&H_N=DES_{M_N}\left(H_N \right) \oplus H_{N-1}\\
		\end{align}
		
		\par
		利用 $Y'=DES_{K'}\left( X'\right) $和$X' \oplus Y'=X\oplus Y$ 两个性质可知，若敌手同时对 $M_1$和 $M_0$逐比特取补，则由性质一知$DES_{M_1}\left( H_0\right) $ 也被逐比特求补，由性质二知$H_1$ 保持不变，所以$H_2,\ldots,H_N$ 也都不受影响，所以有： $H\left( M_1 M_2\ldots M_N\right) =H\left( M_1^{'} M_2 \ldots M_N\right)=H_N $
		\par
		(2)改迭代关系为$H_i=E_{H_{i-1}} \left(M_i \right) \oplus M_i$ ，则敌手也可同时对 $M_1$和 $H_0$逐比特取补，由性质一知 $DES_{H_0}\left( M_1\right) $也被逐比特求补，由性质二知 $H_1,\ldots,H_N$都不受影响，故仍可进行上述攻击。
		
	}

	\begin{Exercise}
		考虑用公钥加密算法构造哈希函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其哈希值为
		$H\left( B_1, B_2\right) =RSA\left( RSA\left( B_1\right) \oplus B_2\right) $。证明对任一分组$C_1$可选$C_2$，使得$H\left( C_1, C_2\right) = H\left( B_1, B_2\right) $。证明用这种攻击法，可攻击上述用公钥加密算法构造的哈希函数。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		对任一分组$C_1$ ，可构造$C_2$ 如下：\\
		\[ C_2=RSA\left( C_1\right) \oplus RSA\left(B_1 \right) \oplus B_2 \]
		则:\\
		\begin{align}
			&H\left(C_1,C_2 \right) \\
			&=RSA\left( RSA\left( C_1\right) \oplus C_2 \right) \\
			&=RSA\left( RSA\left( C_1\right) \oplus RSA\left( C_1\right) \oplus RSA\left( B_1\right) \oplus B_2 \right)\\
			&=RSA\left( RSA\left( B_1\right) \oplus B_2 \right)\\
			&=H\left( B_1,B_2\right) 
		\end{align}
		
		设哈希函数的输入消息分组为 $M_1,M_2,\ldots,M_N$，则可任取$M_1^{'}$ 替代$M_1$ ，并由上述方法构造$M_2^{'}$ 替代$M_2$ ，可得$H\left( M_1^{'},M_2^{'},\ldots,M_N\right) = H\left( M_1,M_2,\ldots,M_N\right)$ ，攻击成功。	
	}

%	\begin{Exercise}
%		在图6-11中，假定有80个32比特长的字用于存储每一个$W_t$，因此在处理信息分组前，可预先计算出这80个值。为节省存储空间，考虑有16个字的循环移位寄存器，其初值存储前16个值（即$W_0，W_1，…, W_{15}$），设计一个算法计算以后的每一个$W_t$。
%		\cite{yang-mcry}
%	\end{Exercise}
%	\jd{
%		 $W_0\sim W_{15}$为消息分组的16个字，初始放在移位寄存器中，如图\ref{fig1}连接电路。$CLS_1$ 的输出反馈到移位寄存器右边的输入端，则每个时钟到来时，移位寄存器从左边输出端移出一个字
%		 $W_i\left( i=0,\ldots ,79\right) $ 。\par
%		 
%	}
%	\begin{figure}[h]
%		\centering
%		\includegraphics[width=\linewidth] {ex6-4.png}
%		\caption{移位寄存器连接图}
%		\label{fig1}
%	\end{figure}

	\begin{Exercise}
		对SHA，计算$W_{16}，W_{17}，W_{18}，W_{19}$.
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		\[ W_{16} = CLS_1 \left( W_0 \oplus W_2 \oplus W_8 \oplus W_{13} \right) \]	 
		\[ W_{17} = CLS_1 \left( W_1 \oplus W_3 \oplus W_9 \oplus W_{14} \right) \]	
		\[ W_{18} = CLS_1 \left( W_2 \oplus W_4 \oplus W_{10} \oplus W_{15} \right) \]	 
		\[ W_{19} = CLS_1 \left( W_3 \oplus W_5 \oplus W_{11} \oplus W_{16} \right) \]	
	}

	\begin{Exercise}
		设$a_1 a_2 a_3 a_4$是32比特长的字中的4个字节，每一给$a_i$可看作由二进制表示的0$\sim$255之间的整数，在大端方式中，该字表示整数$a_1 2^{24}+a_2 2^{16}+a_3 2^8+a_4$，在小端结构中，该字表示整数$a_4 2^{24}+a_3 2^{16}+a_2 2^8+a_1$。
		\cite{yang-mcry}\\
		（1）MD5使用小端结构，因消息的摘要值不应依赖于算法所用的结构，因此在MD5中为了对以大端
		方式存储的两个字$X=x_1 x_2 x_3 x_4$和$Y=y_1 y_2 y_3 y_4$进行模2加法运算，必须要对这两个字进行调整，问如何进行？\\
		（2）SHA使用大端方式，问如何对以小端结构存储的两个字X和Y进行模2加法运算。
		
	\end{Exercise}
	\jd{
		(1)由于MD5使用little-endian结构，而X，Y使用的是big-endian存储结构，因此必须把X，Y转换成little-endian格式，则有:\\
		\begin{align}
			&x_1 2^{24} + x_2 2^{16} + x_3 2^{8} +x_4 \\
			&=x_4^{'} 2^{24} + x_3^{'} 2^{16} + x_2^{'} 2^{8} + x_1^{'}\\
			&\Rightarrow x_1^{'}=x_4,x_2^{'}=x_3,x_3^{'}=x_2,x_4^{'}=x_1
		\end{align}

		\par
		
		(2)由于SHA使用big-endian结构，而X，Y使用的是little-endian存储结构，因此必须把X，Y转换
		成big-endian格式，则有:\\
		\begin{align}
			&x_4 2^{24} + x_3 2^{16} + x_2 2^{8} +x_1 \\
			&=x_1^{'} 2^{24} + x_2^{'} 2^{16} + x_3^{'} 2^{8} + x_4^{'}\\
			&\Rightarrow x_1^{'}=x_4,x_2^{'}=x_3,x_3^{'}=x_2,x_4^{'}=x_1
		\end{align}

	}

\chapter{数字签名}
	\begin{Exercise}
		数字签名能提供的安全属性有哪些？
	\end{Exercise}
	\jd{
		数字签名能够提供身份认证、数据完整性、不可否认性和匿名性方面的安全功能。
	}

	\begin{Exercise}
		在DSS数字签名标准中，$p=83=2\times 41+1,q=41,h=2$，于是$g\equiv {{2}^{2}}\equiv 4\bmod 83$，若取$x=57$，则$y\equiv {{g}^{x}}\equiv {{4}^{57}}=77\bmod 83$。在对消息$M=56$签名时，选择$k=23$，计算签名并进行验证。
		\cite{yang-mcry}\\
	\end{Exercise}
	\jd{
		(1)签名过程：为了简化，用$M$代替$H(M)$，则用户对消息$M$的签名为$(r,s)$。计算:
		\[r=({{g}^{k}}\bmod p)\bmod q=({{4}^{23}}\bmod 83)\bmod 41=51\bmod 41=10 \]
		\[{{k}^{-1}}\bmod q={{23}^{-1}}\bmod 41=25\]
		\[s=[{{k}^{-1}}(M+xr)]\bmod q=[25\times (56+57\times 10)]\bmod 41=29 \]
		所以签名$(r,s)=(10,29)$。
		\par
		
		(2)验证过程：接收方收到的消息为$M'$，签名为$(r',s')=(10,29)$。计算:\\
		$w={{({s}')}^{-1}}\bmod q={{29}^{-1}}\bmod 41=17$，\\
		${{u}_{1}}=(M'w)\bmod q=(56\times 17)\bmod 41=9$，\\
		${{u}_{2}}=(r'w)\bmod q=(10\times 17)\bmod 41=6$，\\
		$v=[({{g}^{{{u}_{1}}}}{{y}^{{{u}_{2}}}})\bmod p]\bmod q=[({{4}^{9}}\times {{77}^{6}})\bmod 83]\bmod 41=10$。\\
		因为$v=r'=10$，所以认为签名有效，即验证通过。
	}

	\begin{Exercise}
		在DSA签名算法中，参数$k$泄露会产生什么后果？
		\cite{yang-mcry}\\
	\end{Exercise}
	\jd{
		若攻击者得到了一个有效签名$(r,s)$，并且知道了DSA签名算法中的参数$k$，那么在签名方程$s=[{{k}^{-1}}(H(M)+xr)]\bmod q$中只存在一个未知数，即用户的秘密钥$x$，所以攻击者可以求得秘密钥$x=[(ks-H(M)){{r}^{-1}}]\bmod q$。因此，参数$k$泄漏将导致签名秘密钥的泄漏，攻击者可以伪造任意消息的签名。
	}



%----------------------
%      参考文献
%----------------------

\bibliographystyle{plain} 
\bibliography{../crybook/chapters/myreference}
	   

\end{document}